Problem F
トリックアンドトリート

ハロウィンの時期になると、子供たちがお菓子を要求して家に寄ってきます。 お菓子をあげないと、怒ってトイレットペーパーを家に投げつけられてしまいますよね！

今年は、近所の子供たちが、$A_1, A_2, \dots , A_ N$人のグループで順番に家にやってくることを知っています。 $A_ i$人のグループが来ると、$A_ i$個のお菓子を要求してきます。 足りないと、トイレットペーパーを1個投げつけて、次の家に移動して、二度と戻ってきません。

そうならないためには、子供たちにお菓子をあげる必要があります。

あなたは、お菓子を$M$個購入することができる予算を持っている場合に、いくつのお菓子を購入すれば投げつけられるトイレットペーパーを最小にすることができるでしょうか。

入力

入力の1行目は、$1 \le N \le 100\, 000$と$1 \le M \le 2 \cdot 10^9$の2つの数が含まれ、それぞれ、子供のグループの数と購入できるお菓子の最大数を表します。

次の$N$行には、家に来る子供たちのグループの人数が、子供たちが来る順で含まれます。 各グループの子供たちは、$1$個から$10$個の間のお菓子を要求します。

出力

単一の整数で、適切にお菓子を購入した場合に投げつけられるトイレットペーパーの最小数を出力します。

採点

あなたのソリューションは、テストグループのセットでテストされ、それぞれにポイントが与えられます。 テストグループのポイントを得るためには、テストグループ内のすべてのテストケースを成功する必要があります。

3 3
3 2 1

2

3 2
1 1 2

1

7 5
2 1 1 4 3 2 5

4