Game Balance

Time Limit : 8 sec, Memory Limit : 262144 KB

ゲームバランス

あなたは冒険ゲームを作成している.このゲームのプレイヤーは,主人公を操作して敵モンスターを倒し,主人公のレベルを上げることで冒険を進めていく.主人公の初期レベルは 1 である.

このゲームには N 種類の敵モンスターが用意されており,弱い順で i 番目の種類の敵モンスターの強さは si である.主人公が 1 回の戦闘を行うときには,次に戦う敵モンスターの種類を自由に選び,ちょうど 1 体の敵モンスターと戦闘を行う.主人公は同じ種類の敵モンスターと何回でも戦うことができ,何回でも倒すことができる.

あなたはいま,このゲームのバランスを調整するために,あるパラメーター X を決めようとしている.パラメーター X は正の整数であり下記のように使われる.

  • 主人公のレベルが L のとき,強さ siL+X 未満の敵は倒せるが,それより強い敵モンスターは倒せない.
  • 主人公のレベルが L のとき,強さ si の敵を倒すと max(1, X-|L-si|) だけ主人公のレベルが上がる.

このゲームは,最も強い(N 種類目の)敵モンスターを初めて倒したときにゲームクリアとなる.あなたは,ゲームクリアまでに必要となる戦闘の回数が最低でも M 回以上となるようにパラメーター X を決めたいと考えている.ただし,敵モンスターの強さの設定によっては,X をどのように設定しても M 回未満の戦闘回数でゲームクリアできてしまうか,ゲームをクリアできなくなってしまう場合があることに注意せよ.

パラメーター X を決めるとき,上記の条件を満たす範囲で最大のパラメーター値 Xmax を計算するプログラムを作ってほしい.

Input

入力は複数のデータセットから構成される.データセットの個数は最大でも 50 を超えない.各データセットは次の形式で表される.

N M
s1 s2 ... sN

1 行目は空白で区切られた 2 つの整数 N, M からなる.N は用意した敵モンスターの種類の数,M はゲームクリアまでに必要となるべき最小の戦闘の数であり,1 ≤ N ≤ 100,000, 2 ≤ M ≤1,000,000 を満たす.

2 行目は空白で区切られた N 個の整数 s1, s2, ..., sN からなり,N 種類の敵モンスターそれぞれの強さを表す.各 si1 ≤ si ≤ 1,000,000 を満たし,また si < si+1 (1 ≤ i ≤ N-1) である.

入力の終わりは空白で区切られた 2 つのゼロからなる行で表される.

Output

各データセットについて,ゲームクリアまでに必要となる戦闘の回数が M 回以上となるパラメーター X の内の最大値 Xmax を整数で出力せよ.X をどのように設定しても M 回未満の戦闘回数でゲームクリアできてしまうかゲームをクリアできなくなってしまうテストケースの場合には -1 のみからなる行を出力せよ.

Sample Input

3 4
1 5 9
1 2
1
2 10
1 1000000
2 4
1 10
0 0

Output for Sample Input

3
-1
499996
4

2 番目のテストケースでは,X = 1 と設定すると 1 回の戦闘でゲームをクリアできてしまう. このケースでは,必要となる戦闘の回数が M 回以上であり,かつゲームをクリアできるように X を設定することが出来ない. よって -1 のみからなる行を出力する.


Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2017, 2017-07-02
http://acm-icpc.aitea.net/