#586. HKMIN – K số nhỏ nhất

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Chưa có dữ liệu
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho hai dãy số nguyên A gồm m số a_1, a_2, …, a_m B gồm n số b_1, b_2, …, b_n . Với mỗi số a_i thuộc dãy A và mỗi số b_j thuộc dãy B người ta tính tổng nó. Tất cả các tổng này sau khi được sắp xếp không giảm sẽ tạo thành dãy C .

Nhiệm vụ của bạn là tìm K số đầu tiên trong dãy C .

Dữ liệu vào:

  • Dòng đầu chứa ba số nguyên dương m, n K ;
  • m dòng tiếp theo chứa m số nguyên dương a_1, a_2, …, a_m ;
  • n dòng cuối chứa n số nguyên dương b_1, b_2, …, b_n ;

Hai số liên tiếp trên cùng một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

  • Ghi K dòng là K số đầu tiên trong dãy C theo thứ tự không giảm.

Ví dụ:

Dữ liệu vào:
4 4 6
1
2
3
4
2
3
4
5
Dữ liệu ra:
3
4
4
5
5
5
Giải thích:
  • Dãy C gồm 16 số theo thứ tự không giảm: 3\ 4\ 4\ 5\ 5\ 5\ 6\ 6\ 6\ 6\ 7\ 7\ 7\ 8\ 8\ 9 .

Giới hạn:

  • 1 ≤ m, n, K ≤ 5×10^4; 1 ≤ a_i , b_i ≤ 10^9 .