Организация 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\)-м стоге, если Бесси будет действовать оптимально!
Выходные данные
Для каждого набора входных данных выведите единственное число: максимальное количество тюков, которые можно получить в \(1\)-м стоге через \(d\) дней, если Бесси будет действовать оптимально.
Примечание
Для первого набора входных данных из примера, ниже описан один из возможных способов получить \(3\) тюка в стоге \(1\):
- В первых день, перенести тюк из стога \(3\) в стог \(2\).
- Во второй день, перенести тюк из стога \(3\) в стог \(2\).
- В третий день, перенести тюк из стога \(2\) в стог \(1\).
- В четвертый день, перенести тюк из стога \(2\) в стог \(1\).
- В пятый день, ничего не делать.
Во втором наборе, Бесси может ничего не делать в первый день и перенести тюк из стога \(2\) в стог \(1\) на второй день.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 5
1 0 3 2
2 2
100 1
1 8
0
|
3
101
0
|