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