题目描述

训练营最后有 n 个关卡，需要按顺序完成。

通过第 i 个关卡需要消耗 a_i 点能量。学生有一个能量背包，最多能存 C 点能量。

如果每天开始时补给 x 点能量，规则如下：

1. 当天开始，背包能量增加 x 点，但不能超过容量 C；
2. 然后挑战当前关卡；
3. 如果当前能量不足 a_i 点，就无法通过；
4. 如果通过，能量减少 a_i 点，剩余能量可以带到下一天。

请你求出最小的 x，使得学生可以按顺序通过所有关卡。

输入保证每个关卡的能量需求都不超过 C，因此一定存在答案。

输入格式

第一行输入两个整数 n 和 C。

第二行输入 n 个整数 a_1, a_2, ..., a_n。

输出格式

输出一行，一个整数，表示最小补给速度 x。

样例

5 10
4 6 3 8 2

6

样例说明

如果每天补给 6 点能量，可以按顺序通过所有关卡。
如果每天补给更少，则会在某个关卡前能量不足。

数据范围

• 1 <= n <= 200000
• 1 <= a_i <= C <= 1000000000