← 返回题目列表

Codeforces · 1307/A

A. 牛和干草捆

中文机器翻译题面 查看原题

美国建筑公司 (USACO) 最近命令 Farmer John 在农场上布置一排 $$$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$$$。她也可能因为懒惰而决定在某些日子里不做任何事情。

Bessie 想要最大化 $$$1$$$ 堆中的干草捆数量(即最大化 $$$a_1$$$),而在 Farmer John 返回之前,她只有 $$$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$$$) — 每堆中的干草堆数量。

输出

对于每个测试用例,输出一个整数:如果 Bessie 表现最佳,$$$d$$$ 天后 $$$1$$$ 堆中的干草堆的最大数量。

示例

输入 #1

3
4 5
1 0 3 2
2 2
100 1
1 8
0

输出 #1

3
101
0

注意

在示例的第一个测试用例中,这是 Bessie 最终得到 $$$3$$$ 干草堆 $$$1$$$ 的一种可能方式:

- 第一天,将干草堆从 $$$3$$$ 堆移到 $$$2$$$ 堆
- 第二天,将干草堆从 $$$3$$$ 堆移到 $$$2$$$ 堆
- 第三天,将干草堆从 $$$2$$$ 堆移到 $$$1$$$ 堆
- 第四天,将干草堆从 $$$2$$$ 堆移到 $$$1$$$ 堆
- 第五天,什么也不做

在样本的第二个测试用例中,Bessie 第一天什么都不做,第二天将干草堆从 $$$2$$$ 堆移到 $$$1$$$ 堆。