C. Квесты
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру. Чтобы повысить уровень персонажа, он может выполнять квесты. В игре есть $$$n$$$ квестов, пронумерованных от $$$1$$$ до $$$n$$$.

Монокарп может выполнять квесты согласно следующим правилам:

  • $$$1$$$-й квест всегда доступен для выполнения;
  • $$$i$$$-й квест доступен для выполнения, если каждый квест $$$j < i$$$ был выполнен хотя бы раз.

Обратите внимание, что Монокарп может выполнять один и тот же квест несколько раз.

За каждое выполнение персонаж получает некоторое количество опыта:

  • за первое выполнение $$$i$$$-го квеста он получает $$$a_i$$$ очков опыта;
  • за каждое последующее выполнение $$$i$$$-го квеста он получает $$$b_i$$$ очков опыта.

Монокарп очень занятой человек, поэтому у него есть свободное время, чтобы выполнить не более $$$k$$$ квестов. Ваша задача — посчитайте максимально возможный суммарный опыт, который Монокарп может получить, если он может выполнить не более $$$k$$$ квестов.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 2 \cdot 10^5$$$) — количество квестов и максимальное количество квестов, которые Монокарп может выполнить, соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^3$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^3$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — максимально возможный суммарный опыт, который Монокарп может получить, если он может выполнить не более $$$k$$$ квестов.

Пример
Входные данные
4
4 7
4 3 1 2
1 1 1 1
3 2
1 2 5
3 1 8
5 5
3 2 4 1 4
2 3 1 4 7
6 4
1 4 5 4 5 10
1 5 1 2 5 1
Выходные данные
13
4
15
15
Примечание

В первом примере одна из возможных последовательностей выполнения квестов следующая: $$$1, 1, 2, 3, 2, 4, 4$$$; суммарный опыт равен $$$\underline{4} + 1 + \underline{3} + \underline{1} + 1 + \underline{2} + 1 = 13$$$ (подчеркнутые числа соответствуют первому выполнению квеста).

Во втором примере одна из возможных последовательностей выполнения квестов следующая: $$$1, 1$$$; суммарный опыт равен $$$\underline{1} + 3 = 4$$$.

В третьем примере одна из возможных последовательностей выполнения квестов следующая: $$$1, 2, 2, 2, 3$$$; суммарный опыт равен $$$\underline{3} + \underline{2} + 3 + 3 + \underline{4} = 15$$$.