У вас есть массив целых чисел \(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\) операций.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество монет, которое вы можете получить выполнив не более \(k\) операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|