У вас есть массив целых чисел $$$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$$$ операций.
44 41 7 5 22 6 5 23 03 5 25 4 75 95 2 5 6 35 9 1 9 76 1411 4 6 2 8 1643 45 9 41 15 38
9 0 30 167
Название |
---|