eolymp
bolt
Try our new interface for solving problems
Məsələlər

Рицарі багатокутного столу

Рицарі багатокутного столу

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

На відміну від Рицарів Круглого Столу, Рицарі Багатокутного Столу не виділяються благородством і з радістю вб'ють один іншого. Проте, кожний рицар володіє своєю силою, і один рицар може вбити іншого тільки якщо його сила більша, ніж сила жертви. Проте, навіть такого рицаря буде мучити совість, тому рицар може вбити максимум k інших людей.

Також, у кожного рицаря є певна кількість монет. При вбивстві рицар може забрати монети своєї жертви.

Кожний рицар задумався: а яка найбільша кількість монет може в нього бути, якщо вбивати інших рицарів буде тільки він.

Вам необхідно відповісти на це питання для кожного рицаря.

Giriş verilənləri

Перший рядок містить два числа n і k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ min(n-1, 30)) – кількість рицарів і число k, описане в умові.

В другому рядку знаходиться n чисел p[1, p[2]p[n] (1 ≤ p[i]10^9) – сили рицарів. Всі p_i різні.

В третьому рядку знаходиться n чисел c[1], c[2]c[n] (1 ≤ c[i]10^9) – кількість монет у рицарів.

Çıxış verilənləri

Виведіть n чисел – найбільшу кількість монет у кожного рицаря.

Nümunə

Giriş verilənləri #1
4 2
4 5 9 7
1 2 11 33
Çıxış verilənləri #1
1 3 46 36
Giriş verilənləri #2
5 1
1 2 3 4 5
1 2 3 4 5
Çıxış verilənləri #2
1 3 5 7 9
Giriş verilənləri #3
1 0
2
3
Çıxış verilənləri #3
3