A. Корова и стоги сена
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Организация USA Construction Operation (USACO) недавно приказала Фермеру Джону разместить у себя на ферме $$$n$$$ стогов сена в ряд. При чем $$$i$$$-й стог сена состоит из $$$a_i$$$ тюков сена.

Однако недавно Фермер Джон уехал на отдых, оставив Бесси саму по себе. Каждый день Бесси, озорная корова, может выбрать один тюк из любого непустого стога и переместить его в соседний стог. Формально, за один день она может выбрать два любых индекса $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$) таких, что $$$|i-j|=1$$$ и $$$a_i>0$$$ и применить $$$a_i = a_i - 1$$$, $$$a_j = a_j + 1$$$. Она также может решить ничего не делать в некоторые дни, потому что Бесси ленивая.

Бесси хочет максимизировать количество тюков в $$$1$$$-м стоге (то есть максимизировать $$$a_1$$$), и у нее есть только $$$d$$$ дней до того как вернется Фермер Джон. Помогите ей определить максимальное количество тюков в $$$1$$$-м стоге, если Бесси будет действовать оптимально!

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

Входные данные содержат несколько наборов входных данных. В первой строке задано единственное число $$$t$$$ ($$$1 \le t \le 100$$$)  — количество наборов входных данных. Следующие $$$2t$$$ строк содержат описания наборов  — по две строки на набор.

В первой строке каждого набора входных данных задано два целых числа $$$n$$$ и $$$d$$$ ($$$1 \le n,d \le 100$$$) — количество стогов сена и количество оставшихся дней, соответственно.

Во второй строке каждого набора задано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$)  — количество тюков в каждом стоге.

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

Для каждого набора входных данных выведите единственное число: максимальное количество тюков, которые можно получить в $$$1$$$-м стоге через $$$d$$$ дней, если Бесси будет действовать оптимально.

Пример
Входные данные
3
4 5
1 0 3 2
2 2
100 1
1 8
0
Выходные данные
3
101
0
Примечание

Для первого набора входных данных из примера, ниже описан один из возможных способов получить $$$3$$$ тюка в стоге $$$1$$$:

  • В первых день, перенести тюк из стога $$$3$$$ в стог $$$2$$$.
  • Во второй день, перенести тюк из стога $$$3$$$ в стог $$$2$$$.
  • В третий день, перенести тюк из стога $$$2$$$ в стог $$$1$$$.
  • В четвертый день, перенести тюк из стога $$$2$$$ в стог $$$1$$$.
  • В пятый день, ничего не делать.

Во втором наборе, Бесси может ничего не делать в первый день и перенести тюк из стога $$$2$$$ в стог $$$1$$$ на второй день.