配点 : 100 点
問題文
1, 2, ..., N 可以得到第 N 个甜菜按顺序种植。 甜菜 i 能够获得的最大水量为 A_i 。A_i 如果给予超过该量的水,这些甜菜会因吸水过多而枯死。
现在开始最大 M 通过一次喷灌操作,可以给甜菜浇水。使用喷灌器的话, 1 可以通过一次操作选择连续的范围,均匀地给该范围内的甜菜浇水。 1 。
希望通过喷灌操作尽可能给甜菜们浇更多的水。在不让任何甜菜枯死的条件下,求能给甜菜们浇水量的总和的最大值。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^{14}
- 1 \leq A_i \leq 10^9
- i \neq j 如果 A_i \neq A_j
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 ... A_N
出力
输出能够给甜菜们浇水量总和的最大值。
入力例 1
4 4 1 4 2 5
出力例 1
9
例如,可以像下面这样进行喷灌操作。
- 区間 [1, 4] 给浇水(总计 4)。
- 区間 [2, 4] 给浇水(总计 7)。
- 区間 [2, 2] 给浇水(总计 8)。
- 区間 [4, 4] 给浇水(总计 9)。
入力例 2
4 6 10 9 4 11
出力例 2
20
入力例 3
1 100000000000000 1
出力例 3
1