G. Хороший ключ, плохой ключ
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ сундуков. $$$i$$$-й сундук содержит $$$a_i$$$ монет. Вы должны открыть все $$$n$$$ сундуков по порядку, начиная с сундука $$$1$$$, заканчивая сундуком $$$n$$$.

Также существуют два вида ключей, которые вы можете использовать для открытия каждого сундука:

  • хороший ключ, который стоит $$$k$$$ монет;
  • плохой ключ, который бесплатен, но уменьшит вдвое количество монет в каждом неоткрытом сундуке, включая сундук, который собираются им открыть. Уменьшаясь вдвое, количество монет округляется вниз до ближайшего целого числа для каждого из сундуков. Иными словами, если используется плохой ключ, чтобы открыть сундук $$$i$$$, количества монет в сундуках изменятся следующим образом: $$$a_i = \lfloor{\frac{a_i}{2}\rfloor}$$$, $$$a_{i+1} = \lfloor\frac{a_{i+1}}{2}\rfloor, \dots, a_n = \lfloor \frac{a_n}{2}\rfloor$$$;
  • любой ключ (и хороший и плохой) ломается после использования, то есть является одноразовым.

Вам необходимо использовать $$$n$$$ ключей, по одному на каждый сундук. Изначально у вас нет ключей и монет. Если вы хотите использовать хороший ключ, то его надо купить.

В процессе вы можете уходить в минус — например, если у вас есть $$$1$$$ монета, вы можете купить хороший ключ за $$$k=3$$$ монеты, и у вас станет $$$-2$$$ монеты.

Найдите максимальное количество монет, которое вы сможете получить в итоге после открытия всех $$$n$$$ сундуков по порядку от $$$1$$$ до $$$n$$$.

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

В первой строке содержится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора содержатся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq k \leq 10^9$$$) — количество сундуков и стоимость хорошего ключа соответственно.

Вторая строка каждого набора содержит $$$n$$$ чисел $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$)  — количество монет в каждом из сундуков.

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

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

Для каждого набора выведите одно число  — максимальное количество монет, которое вы сможете получить после открытия сундуков с $$$1$$$ по $$$n$$$.

Пожалуйста, обратите внимание, что ответ для некоторых наборов входных данных может не поместиться в 32-разрядный целочисленный тип, поэтому вы должны использовать по крайней мере 64-разрядный целочисленный тип в вашем языке программирования (например, long long для C++).

Пример
Входные данные
5
4 5
10 10 3 1
1 2
1
3 12
10 10 29
12 51
5 74 89 45 18 69 67 67 11 96 23 59
2 57
85 60
Выходные данные
11
0
13
60
58
Примечание

В первом наборе одна из возможных стратегий следующая:

  • Купить хороший ключ за $$$5$$$ монет, и открыть сундук $$$1$$$, получив $$$10$$$ монет. Ваш баланс станет $$$0 + 10 - 5 = 5$$$ монет.
  • Купить хороший ключ за $$$5$$$ монет, и открыть сундук $$$2$$$, получив $$$10$$$ монет. Ваш баланс станет $$$5 + 10 - 5 = 10$$$ монет.
  • Использовать плохой ключ, и открыть им сундук $$$3$$$. В результате использования плохого ключа, количество монет в сундуке $$$3$$$ становится $$$\left\lfloor \frac{3}{2} \right\rfloor = 1$$$, и количество монет в сундуке $$$4$$$ становится $$$\left\lfloor \frac{1}{2} \right\rfloor = 0$$$. Ваш баланс станет $$$10 + 1 = 11$$$.
  • Использовать плохой ключ, и открыть им сундук $$$4$$$. В результате использования плохого ключа, количество монет в сундуке $$$4$$$ станет $$$\left\lfloor \frac{0}{2} \right\rfloor = 0$$$. Ваш баланс станет $$$11 + 0 = 11$$$.
После открытия всех сундуков, у вас останется $$$11$$$ монет. Можно доказать, что получить больше монет невозможно.