Problem D: Smell Searcher

Problem

廃津大学では強烈な香りを放つN個の廃材が一列に並んでいます。 廃材には1からNの番号が順番にふられていて、i番目の廃材は強さa_iの香りを放っています。

リヒト君は仕事で、すべての廃材の放つ香りの総和を求めるよう依頼されました。 香りの総和がM以上になると「大変きつい仕事」とみなされ特別支給金がもらえます。

この仕事を行うために、リヒト君は精度Rの香り検出器を使います。 精度Rの香り検出器を使うとi番目の廃材の香りを測ろうとすると同時にi−R,i−R+1,...,i−1,i,i+1,...,i+R−1,i+R番目の廃材の香りも検出されます。言い換えると、閉区間[ max(i−R,1), min(i+R,N) ] の廃材の香りを検出します。ここで、max(a,b)はaとbの最大値、min(a,b)はaとbの最小値を表します。 ただし、測った廃材の1つ隣の廃材の香りの強さは本来の香りの強さよりC減らされ、2つ隣の廃材の強さ香りは本来の香りの強さより2*C減らされて検出されます。つまり、j(0≤j≤R)個隣にある廃材の香りの強さは a_i − j * C として検出されます。結果的に、i番目の廃材に精度Rの検出器を使うことで検出された香りの強さの最大値がi番目の廃材の香りの強さとして認識されます。

精度の高い検出器を使うとその分費用がかかるため、リヒト君は検出器が認識した1からN番目の廃材の香りの総和がM以上になる最低の精度Rの値を知りたいと思っています。

Input

入力は以下の形式で与えられる。

N M C
a1 a2 ... aN

1行目に、1つの整数N,M,Cが空白区切りで与えられる。2行目にNつの整数が空白区切りで与えられる。a_iはi番目の廃材の香りの強さを表す。

Constraints

入力は以下の制約を満たす。

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10¹⁴
• 1 ≤ C ≤ 10⁹
• 0 ≤ a_i ≤ 10⁹ (1 ≤ i ≤ N)

Output

精度Rの検出器を使って認識される廃材の香りの総和をM以上にしたときのRの最小値を出力せよ。 それが不可能な場合は−1を出力せよ。 Rは必ず0以上であり、負の値の精度は存在しない。

Sample Input1

6 25 3
8 5 1 1 2 6

Sample Output1

1

このとき、精度0の検出器を使うと 8 + 5 + 1 + 1 + 2 + 6 = 23　で25以上になりません。 精度1の検出器を使うと max(8,5-3) + max(8-3,5,1-3) + max(5-3,1,1-3) + max(1-3,1,2-3) + max(1-3,2,6-3) + max(2-3,6) = 8 + 5 + 2 + 1 + 3 + 6 = 25 で25以上になるので1が正解です。

Sample Input2

4 10 1
1 2 3 4

Sample Output2

0

Sample Input3

4 11 1
1 2 3 4

Sample Output3

-1