У вас есть массив целых чисел \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач