B. Рыцари многоугольного стола
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В отличие от Рыцарей Круглого Стола, Рыцари Многоугольного Стола обделены благородством и с радостью убьют друг друга. Однако каждый рыцарь обладает своей силой, и один рыцарь может убить другого только если его сила больше, чем сила жертвы. Однако даже такого рыцаря будет мучить совесть, поэтому рыцарь может убить максимум $$$k$$$ других рыцарей.

Также у каждого рыцаря есть некоторое количество монет. При убийстве рыцарь может забрать все монеты своей жертвы.

Сейчас каждый рыцарь задумался: а какое наибольшее количество монет у него может оказаться, если убивать других рыцарей будет только он?

Вам предстоит ответить на этот вопрос для каждого рыцаря.

Входные данные

В первой строке даны два числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 10^5, 0 \le k \le \min(n-1,10))$$$ — количество рыцарей и число $$$k$$$, описанное в условии.

Во второй строке записаны $$$n$$$ чисел $$$p_1, p_2 ,\ldots,p_n$$$ $$$(1 \le p_i \le 10^9)$$$ — силы рыцарей. Все $$$p_i$$$ различны.

В третьей строке записаны $$$n$$$ чисел $$$c_1, c_2 ,\ldots,c_n$$$ $$$(0 \le c_i \le 10^9)$$$ — количества монет у рыцарей.

Выходные данные

Выведите $$$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
Примечание

Рассмотрим первый пример.

  • Первый рыцарь самый слабый, он не может никого убить, поэтому у него максимум может быть только одна монета.
  • Второй рыцарь может убить первого и забрать его монету в дополнение к двум своим.
  • Третий рыцарь сильнее всех, но так как он максимум может убить $$$k = 2$$$ рыцарей, то выгоднее всего забрать монеты у второго и четвертого рыцаря: $$$2+11+33 = 46$$$.
  • Четвертый рыцарь должен забрать монеты у первого и второго: $$$33+1+2 = 36$$$.

Во втором примере первый рыцарь не может никого убить, а все остальные должны убить одного рыцаря, имеющего номер, на один меньший.

В третьем примере всего один рыцарь, он не может никого убить, хотя очень хочет.