F. Подели пополам или вычти
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$. Также вам дано положительное целое число $$$b$$$.

Мы можете сделать следующие операции несколько раз в любом порядке:

  1. Выберите некоторый индекс $$$1 \le i \le n$$$ и замените $$$a_i$$$ на $$$\lceil \frac{a_i}{2} \rceil$$$. Здесь $$$\lceil x \rceil$$$ обозначает минимальное целое число не меньше чем $$$x$$$.
  2. Выберите некоторый индекс $$$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$$$, которую можно получить, выполняя эти операции.

Входные данные

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Описания наборов входных данных следуют.

В первой строке описания каждого набора входных данных находится четыре целых числа $$$n$$$, $$$b$$$, $$$k_1$$$, $$$k_2$$$ ($$$1 \le n \le 5000$$$, $$$1 \le b \le 10^9$$$, $$$0 \le k_1, k_2 \le n$$$).

Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ задающих массив $$$a$$$ ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите минимальную цену массива $$$a$$$, которую можно получить, выполняя операции.

Пример
Входные данные
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
Примечание

В первом наборе входных данных вы можете сделать следующее:

  • Сделать операцию 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$$$. Можно показать, что это минимальная достижимая цена.