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

У вас есть массив целых чисел $$$a$$$ размера $$$n$$$. Изначально все элементы массива равны $$$1$$$. Вы можете выполнять операцию следующего вида: выбрать два целых числа $$$i$$$ ($$$1 \le i \le n$$$) и $$$x$$$ ($$$x > 0$$$), а затем увеличить значение $$$a_i$$$ на $$$\left\lfloor\frac{a_i}{x}\right\rfloor$$$ (т.е. сделать $$$a_i = a_i + \left\lfloor\frac{a_i}{x}\right\rfloor$$$).

После выполнения всех операций вы получите $$$c_i$$$ монет для тех $$$i$$$, в которых $$$a_i = b_i$$$.

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

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

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

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

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

Третья строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^3$$$.

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

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

Пример
Входные данные
4
4 4
1 7 5 2
2 6 5 2
3 0
3 5 2
5 4 7
5 9
5 2 5 6 3
5 9 1 9 7
6 14
11 4 6 2 8 16
43 45 9 41 15 38
Выходные данные
9
0
30
167