問題文

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
• 入力は全て整数

入力例 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