山区里有一座小型水库,主要用来给下游的农田供水。雨季来临前水库是空的,接下来的 n 天里每天都会有一定量的雨水汇入。
水库每天的调度规则是这样的:先开闸下泄,再接纳当天的来水。闸门有一个固定的最大流量,设为 x 吨/天,也就是这一天最多能泄掉 x 吨水;当然,实际泄水量不能超过当时库里的存水。当天的来水量为 a_i 吨,泄完之后这些水会全部流入水库。
水库的总容量是 V 吨。为了保证大坝安全,任何时刻库里的蓄水量都不能超过 V,包括当天的来水汇入之后的那一瞬间。
管理人员不希望闸门开得太大,以免下游被淹。请你求出满足安全要求的最小闸门流量 x。题目保证一定存在满足要求的 x。
第一行,两个整数 n、V,分别表示天数和水库容量。
第二行,n 个整数 a_1, a_2, ..., a_n,表示每天的来水量。
输出一个整数,表示满足要求的最小闸门流量 x。
3 10 4 6 5
3
2 5 3 3
1
1 100 7
0
对于 30% 的数据,1 ≤ n ≤ 1000,1 ≤ V ≤ 10^4,1 ≤ a_i ≤ V。
对于 100% 的数据,1 ≤ n ≤ 2 × 10^5,1 ≤ V ≤ 10^9,1 ≤ a_i ≤ V。