Лицарі багатокутного столу
Лицарі багатокутного столу
На відміну від Лицарів Круглого Столу, Лицарі Багатокутного Столу не виділяються благородством і з радістю вб'ють один іншого. Проте, кожний лицар володіє своєю силою, і один лицар може вбити іншого тільки якщо його сила більша, ніж сила жертви. Проте, навіть такого лицаря буде мучити совість, тому лицар може вбити максимум k інших людей.
Також, у кожного лицаря є певна кількість монет. При вбивстві лицар може забрати монети своєї жертви.
Кожний лицар задумався: а яка найбільша кількість монет може в нього бути, якщо вбивати інших лицарів буде тільки він.
Вам необхідно відповісти на це питання для кожного лицаря.
Вхідні дані:
Перший рядок містить два числа n і k (**1 ≤ n ≤ 105
**, 0 ≤ k ≤ min(n-1, 30)) – кількість лицарів і число k, описане в умові.
В другому рядку знаходиться n чисел p[1
, p2
… pn
(**1 ≤ pi
≤ 109
**) – сили лицарів. Всі p_i різні.
В третьому рядку знаходиться n чисел c1
, c2
… cn
(**1 ≤ ci
≤ 109
**) – кількість монет у лицарів.
Вихідні дані:
Виведіть n чисел – найбільшу кількість монет у кожного лицаря.
4 2 4 5 9 7 1 2 11 33
1 3 46 36
5 1 1 2 3 4 5 1 2 3 4 5
1 3 5 7 9
1 0 2 3
3