B - Sprinkler
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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