← 返回题目列表

AtCoder · ukuku09_b

B. 洒水装置

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

配点 : 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