#847. CHOOSE - Chọn mua hàng

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: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Để tích lũy hàng trong mùa dịch COVID, Tèo đang cần mua hai loại mặt hàng A B . Qua tìm hiểu trên mạng, Tèo đã lập được danh sách gồm n mặt hàng loại A (đánh số từ 1 đến n , mặt hàng thứ i có giá là A_i ) và n mặt hàng loại B (đánh số từ 1 đến n , mặt hàng thứ i có giá là B_i ).

Nếu Tèo chọn mua mặt hàng loại A thứ i và mặt hàng loại B thứ j thì Tèo sẽ phải trả số tiền là A_i+B_j . Tèo rất muốn biết trong n^2 sự lựa chọn của mình, nếu đem số tiền phải trả trong các sự lựa chọn đó sắp xếp không giảm thì k sự lựa chọn đầu tiên sẽ có số tiền lần lượt như thế nào.

Yêu cầu: Cho biết n,k và hai dãy số nguyên dương A_1,A_2,…,A_n , B_1,B_2,…,B_n . Hãy in ra dãy k số (không giảm) là tổng số tiền phải trả của k sự lựa chọn đầu tiên.

Dữ liệu vào:

  • Dòng đầu tiên gồm hai số nguyên n,k (1≤n,k≤10^5;k≤n^2) ;
  • Dòng thứ hai gồm một dãy n số nguyên dương A_1,A_2,…,A_n\ (1≤A_i≤10^9) ;
  • Dòng thứ ba gồm một dãy n số nguyên dương B_1,B_2,…,B_n\ (1≤B_i≤10^9) .

Dữ liệu ra:

  • Một dòng gồm k số nguyên là đáp số bài toán.

Ví dụ:

Dữ liệu vào:
3 4
1 5 2
2 4 6
Dữ liệu ra:
3 4 5 6
Giải thích:

9 sự lựa chọn với số tiền (sau khi sắp xếp không giảm) là: 3, 4, 5, 6, 7, 7, 8, 9, 11 . Trong đó 4 sự lựa chọn đầu tiên là: 3, 4, 5, 6 .

Giới hạn:

  • 80\% số điểm của bài có 1≤n≤1000 ;
  • 20\% số điểm còn lại của bài không có ràng buộc gì thêm.