追記 : 初期の問題において非常に不明瞭な点が存在しました。Writerとして謝罪します。

Rein君は家のリフォームをしています。 家にはNN段の階段があり、ii段目の高さはAicmA_i \hspace{0.25em} \mathrm{cm}です。

家はとても古くii段目とi+1i+1段目との高さの差が場所によってバラバラなことがあります。 そこでRein君はリフォーム中に余った木材を用いて以下の操作を行うことにしました。

  • あるM(1MN)M (1 \le M \le N)を自由に選びAMA_M段目の階段の高さを1cm1\hspace{0.25em} \mathrm{cm}だけ高くする

Rein君の計算によると、余った木材で最大KK回までこの操作を行うことができるとわかっています。

3/10,21:18問題文を修正しました。このブロック内の文章は正しい題意ではありません
Rein君が$1 \le i \le j \le N-1$なるすべての$(i, j)$の組に対し$A_{i+1}-A_i = A_{j+1}-A_j$かつ$i < j$ならば$A_i < A_j$となるように操作を行えるか判定してください。

Rein君がそのように操作を行い、操作完了後ある正整数xxが存在し11以上NN以下の任意の整数の組(i,j)(i, j)についてAi+x(ji)=AjA_i+x(j-i) = A_jとなるように操作を行うことができるか判定してください。

また、もしそのような操作が可能であるならば最小の操作回数を教えて下さい。

Constraints

  • 2N1032 \le N \le 10^3
  • 0K10120 \le K \le 10^{12}
  • 1Ai1091 \le A_i \le 10^{9}

Input

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

NKN \hspace{0.5em} K
A1A2A3ANA_1 \hspace{0.5em} A_2 \hspace{0.5em} A_3 \hspace{0.5em} \cdots \hspace{0.5em} A_N

Output

条件を満たすように操作が可能ならばその操作回数の最小値を出力せよ。不可能ならば-1を出力しそれを報告せよ

Examples

Example1

input1
5 10
1 3 7 5 13
output1
6

A2A_2に1, A4A_4に5だけ高さを足すことで条件を満たすことができます。

Example2

input2
10 5
1 1 1 1 1 2 3 4 5 6
output2
-1

どのように操作を行っても5回以内の操作で条件を満たすような操作は行えません。

Example3

input3
5 10
1 1 1 1 1
output3
10

提出


Go (1.21)