F. Бомба
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Искорка дает вам два массива $$$a$$$ и $$$b$$$ длиной $$$n$$$. Изначально ваш счет равен $$$0$$$. За одну операцию вы можете выбрать целое число $$$i$$$ и добавить $$$a_i$$$ к вашему счету. Затем вы должны установить $$$a_i$$$ = $$$\max(0, a_i - b_i)$$$.

У вас есть время выполнить $$$k$$$ операций, прежде чем Искорка подорвет ядерную бомбу! Каков максимальный счет, который вы можете набрать после $$$k$$$ операций?

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

Первая строка содержит $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

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

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, ... b_n$$$ ($$$1 \leq b_i \leq 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
3 4
5 6 7
2 3 4
5 9
32 52 68 64 14
18 14 53 24 8
5 1000
1 2 3 4 5
5 4 3 2 1
1 1000000
1000000
1
10 6
3 3 5 10 6 8 6 8 7 7
6 1 7 4 1 1 8 9 3 1
Выходные данные
21
349
27
500000500000
47