Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Khác với Hiệp sĩ thành Tron, Hiệp sĩ Ba Lan tước đi sự quý phái và hạnh phúc khi giao đấu với nhau. Mỗi hiệp sĩ có một chỉ số sức mạnh và chiến thắng một hiệp sĩ khác khi và chỉ khi sức mạnh của anh ta lớn hơn sức mạnh của đối phương.

Tuy nhiên theo quy định của quốc vương thì mỗi hiệp sĩ được giao đấu với không quá ~k~ hiệp sĩ khác. Ngoài ra, mỗi hiệp sĩ có một số lượng tiền. Sau khi chiến thắng đối thủ, một hiệp sĩ có thể giành được tiền thưởng là số tiền của đối thủ.

Bây giờ mỗi hiệp sĩ suy ngẫm: anh ta có thể có bao nhiêu tiền nếu giao đấu với các hiệp sĩ khác. Bạn nên trả lời câu hỏi này cho mỗi hiệp sĩ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le n \le 10^5,\ 0 \le k \le \min(n - 1, 10))~ – số hiệp sĩ và số ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2, \ldots, p_n~ ~(1 \le p_i \le 10^9)~ – sức mạnh của các hiệp sĩ. Sức mạnh của ~n~ hiệp sĩ khác nhau từng đôi một.
• Dòng thứ ba chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ ~(0 \le c_i \le 10^9)~ – số lượng tiền mỗi hiệp sĩ có.

Kết quả

• In ~n~ số nguyên – số tiền tối đa mà mỗi hiệp sĩ có thể có nếu anh ta giao đấu với tối đa ~k~ hiệp sĩ khác.

Sample Input 1

4 2
4 5 9 7
1 2 11 33

Sample Output 1

1 3 46 36

Sample Input 2

5 1
1 2 3 4 5
1 2 3 4 5

Sample Output 2

1 3 5 7 9

Sample Input 3

1 0
2
3

Sample Output 3

3

Nguồn: VinhDinhCoder.