ゲームバランス

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

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

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

このゲームは，最も強い（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 種類の敵モンスターそれぞれの強さを表す．各 si は 1 ≤ 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 のみからなる行を出力する．