У вас есть массив положительных целых чисел \(a_1, a_2, \ldots, a_n\) длины \(n\). Также вам дано положительное целое число \(b\).
Мы можете сделать следующие операции несколько раз в любом порядке:
- Выберите некоторый индекс \(1 \le i \le n\) и замените \(a_i\) на \(\lceil \frac{a_i}{2} \rceil\). Здесь \(\lceil x \rceil\) обозначает минимальное целое число не меньше чем \(x\).
- Выберите некоторый индекс \(1 \le i \le n\) и замените \(a_i\) на \(\max(a_i - b, 0)\).
Однако также нужно, чтобы следующие условия удовлетворялись:
- Вы можете сделать не более \(k_1\) операций типа 1.
- Вы можете сделать не более \(k_2\) операций типа 2.
- Для всех \(1 \le i \le n\), вы можете сделать не более \(1\) операции типа 1 с элементом \(a_i\).
- Для всех \(1 \le i \le n\), вы можете сделать не более \(1\) операции типа 2 с элементом \(a_i\).
Цена массива это сумма его элементов. Найдите минимальную цену массива \(a\), которую можно получить, выполняя эти операции.
Выходные данные
Для каждого набора входных данных выведите минимальную цену массива \(a\), которую можно получить, выполняя операции.
Примечание
В первом наборе входных данных вы можете сделать следующее:
- Сделать операцию 2 с элементом \(a_3\). Он поменяется с \(5\) на \(3\).
- Сделать операцию 1 с элементом \(a_1\). Он поменяется с \(9\) на \(5\).
После всех операций получается массив \(a = [5, 3, 3]\) который имеет цену \(5 + 3 + 3 = 11\). Можно показать, что это минимальная достижимая цена.
Во втором наборе входных данных обратите внимание, что нам не разрешено применять операцию типа 1 более одного раза с элементом \(a_1\). Поэтому оптимально применить операцию типа 1 к элементам \(a_1\) и \(a_2\). Также можно применить операцию 1 только к \(a_1\), потому что эта операция никак не меняет элемент \(a_2\).
В третьем наборе входных данных можно получить массив стоимости \(23\):
- Сделать операцию 1 с элементом \(a_4\). Он поменяется с \(19\) на \(10\).
- Сделать операцию 2 с элементом \(a_4\). Он поменяется с \(10\) на \(7\).
После всех операций получается массив \(a = [2, 8, 3, 7, 3]\). Цена массива \(a\) это \(2 + 8 + 3 + 7 + 3 = 23\). Можно показать, что это минимальная достижимая цена.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 2 1 1
9 3 5
2 1 2 0
1000000000 1
5 3 1 1
2 8 3 19 3
6 9 4 2
1 2 3 4 5 6
3 10 3 3
1 2 3
5 1 0 0
999999999 999999999 999999999 999999999 999999999
5 5 4 3
5 9 10 7 4
|
11
500000001
23
6
0
4999999995
6
|