题目描述

小灰灰准备把一排仓库里的货物装箱．共有 $n$ 个仓库，从左到右编号为 $1,2,\ldots,n$，第 $i$ 个仓库最初有 $a_i$ 件货物．

装箱前，可以选出若干对相邻的仓库．每个仓库至多属于其中一对，也可以不属于任何一对．对于选中的每一对仓库，可以把若干件货物从其中一个仓库搬到另一个仓库．搬运后，每个仓库的货物数量都必须非负．所有仓库之间搬运的货物总件数不能超过 $B$．

随后，每个仓库分别装箱，不同仓库的货物不能装进同一个箱子．所有箱子必须装有相同数量的货物，且不能剩下未装箱的货物．空仓库不需要使用箱子．

每个箱子至少装一件货物．请问，每个箱子最多可以装多少件货物？

输入格式

第一行输入两个整数 $n,B$，分别表示仓库数量和最多允许搬运的货物件数．

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各仓库的初始货物数量．

输出格式

输出一个整数，表示每个箱子最多可以装的货物件数．

样例 1

输入

4 3
5 7 8 4

输出

6

解释

选中仓库对 $(1,2)$ 和 $(3,4)$．从仓库 $2$ 向仓库 $1$ 搬运一件货物，从仓库 $3$ 向仓库 $4$ 搬运两件货物．

共搬运三件货物，四个仓库各有六件货物，可以分别装入一个箱子．

样例 2

输入

4 3
5 8 7 4

输出

1

样例 3

输入

2 3
3 5

输出

8

解释

把仓库 $1$ 的三件货物全部搬到仓库 $2$．仓库 $1$ 变为空仓库，仓库 $2$ 的八件货物装入一个箱子．

数据范围

记 $S=\sum_{i=1}^n a_i$．对于所有数据，保证 $1\le n\le2\times10^5$，$1\le a_i\le10^6$，$0\le B\le10^9$．

本题采用捆绑测试，各子任务相互独立．通过一个子任务的全部测试点，才能获得该子任务的分数．

子任务	分数	附加限制
1	10	$n\le6$，$S\le24$
2	20	$S\le2000$
3	15	$B=0$
4		$n\le2$
5	40	无

下发样例

• Data/sample1.in 与 Data/sample1.ans：题面中的样例 1．

• Data/sample2.in 与 Data/sample2.ans：题面中的样例 2．

• Data/sample3.in 与 Data/sample3.ans：题面中的样例 3．

• Data/sample4.in 与 Data/sample4.ans：满足子任务 1 的附加限制．

• Data/sample5.in 与 Data/sample5.ans：满足子任务 2 的附加限制．

• Data/sample6.in 与 Data/sample6.ans：满足子任务 3 的附加限制．

• Data/sample7.in 与 Data/sample7.ans：满足子任务 4 的附加限制．

• Data/sample8.in 与 Data/sample8.ans：该样例无特殊限制．

• Data/sample9.in 与 Data/sample9.ans：该样例无特殊限制．

• Data/sample10.in 与 Data/sample10.ans：该样例无特殊限制．

大样例下载

点击下载本题选手目录