{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003eゲームバランス\u003c/h3\u003e\n\n\u003cp\u003eあなたは冒険ゲームを作成している.このゲームのプレイヤーは,主人公を操作して敵モンスターを倒し,主人公のレベルを上げることで冒険を進めていく.主人公の初期レベルは 1 である.\n\u003c/p\u003e\n\n\u003cp\u003eこのゲームには \u003ci\u003eN\u003c/i\u003e 種類の敵モンスターが用意されており,弱い順で \u003ci\u003ei\u003c/i\u003e 番目の種類の敵モンスターの強さは \u003ci\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e である.主人公が 1 回の戦闘を行うときには,次に戦う敵モンスターの種類を自由に選び,ちょうど 1 体の敵モンスターと戦闘を行う.主人公は同じ種類の敵モンスターと何回でも戦うことができ,何回でも倒すことができる.\n\u003c/p\u003e\n\n\u003cp\u003eあなたはいま,このゲームのバランスを調整するために,あるパラメーター \u003ci\u003eX\u003c/i\u003e を決めようとしている.パラメーター \u003ci\u003eX\u003c/i\u003e は正の整数であり下記のように使われる.\n\u003c/p\u003e\n\n\u003cul\u003e\u003cli\u003e 主人公のレベルが \u003ci\u003eL\u003c/i\u003e のとき,強さ \u003ci\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e が \u003ci\u003eL+X\u003c/i\u003e 未満の敵は倒せるが,それより強い敵モンスターは倒せない.\n\u003c/li\u003e\u003cli\u003e 主人公のレベルが \u003ci\u003eL\u003c/i\u003e のとき,強さ \u003ci\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e の敵を倒すと \u003ci\u003emax(1, X-|L-s\u003csub\u003ei\u003c/sub\u003e|)\u003c/i\u003e だけ主人公のレベルが上がる.\n\u003c/li\u003e\u003c/ul\u003e\n\n\u003cp\u003eこのゲームは,最も強い(\u003ci\u003eN\u003c/i\u003e 種類目の)敵モンスターを初めて倒したときにゲームクリアとなる.あなたは,ゲームクリアまでに必要となる戦闘の回数が最低でも \u003ci\u003eM\u003c/i\u003e 回以上となるようにパラメーター \u003ci\u003eX\u003c/i\u003e を決めたいと考えている.ただし,敵モンスターの強さの設定によっては,\u003ci\u003eX\u003c/i\u003e をどのように設定しても \u003ci\u003eM\u003c/i\u003e 回未満の戦闘回数でゲームクリアできてしまうか,ゲームをクリアできなくなってしまう場合があることに注意せよ.\n\u003c/p\u003e\n\n\u003cp\u003eパラメーター \u003ci\u003eX\u003c/i\u003e を決めるとき,上記の条件を満たす範囲で最大のパラメーター値 \u003ci\u003eX\u003csub\u003emax\u003c/sub\u003e\u003c/i\u003e を計算するプログラムを作ってほしい.\n\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e入力は複数のデータセットから構成される.データセットの個数は最大でも 50 を超えない.各データセットは次の形式で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003ci\u003eN\u003c/i\u003e \u003ci\u003eM\u003c/i\u003e\u003cbr\u003e\u003ci\u003es\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003es\u003csub\u003e2\u003c/sub\u003e\u003c/i\u003e ... \u003ci\u003es\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\u003cp\u003e1 行目は空白で区切られた 2 つの整数 \u003ci\u003eN, M\u003c/i\u003e からなる.\u003ci\u003eN\u003c/i\u003e は用意した敵モンスターの種類の数,\u003ci\u003eM\u003c/i\u003e はゲームクリアまでに必要となるべき最小の戦闘の数であり,\u003ci\u003e1 ≤ N ≤ 100,000\u003c/i\u003e, \u003ci\u003e2 ≤ M ≤1,000,000\u003c/i\u003e を満たす.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e2 行目は空白で区切られた \u003ci\u003eN\u003c/i\u003e 個の整数 \u003ci\u003es\u003csub\u003e1\u003c/sub\u003e, s\u003csub\u003e2\u003c/sub\u003e, ..., s\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e からなり,\u003ci\u003eN\u003c/i\u003e 種類の敵モンスターそれぞれの強さを表す.各 \u003ci\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e は \u003ci\u003e1 ≤ s\u003csub\u003ei\u003c/sub\u003e ≤ 1,000,000\u003c/i\u003e を満たし,また \u003ci\u003es\u003csub\u003ei\u003c/sub\u003e \u0026lt; s\u003csub\u003ei+1\u003c/sub\u003e\u003c/i\u003e (\u003ci\u003e1 ≤ i ≤ N-1\u003c/i\u003e) である.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e入力の終わりは空白で区切られた 2 つのゼロからなる行で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e各データセットについて,ゲームクリアまでに必要となる戦闘の回数が \u003ci\u003eM\u003c/i\u003e 回以上となるパラメーター \u003ci\u003eX\u003c/i\u003e の内の最大値 \u003ci\u003eX\u003csub\u003emax\u003csub\u003e\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e を整数で出力せよ.\u003ci\u003eX\u003c/i\u003e をどのように設定しても \u003ci\u003eM\u003c/i\u003e 回未満の戦闘回数でゲームクリアできてしまうかゲームをクリアできなくなってしまうテストケースの場合には \u003ci\u003e-1\u003c/i\u003e のみからなる行を出力せよ.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\n\n\u003ch3\u003eSample Input\u003c/h3\u003e\n\n\u003cpre\u003e3 4\n1 5 9\n1 2\n1\n2 10\n1 1000000\n2 4\n1 10\n0 0\n\u003c/pre\u003e\n\n\u003ch3\u003eOutput for Sample Input\u003c/h3\u003e\n\n\u003cpre\u003e3\n-1\n499996\n4\u003c/pre\u003e\n\n\u003cp\u003e \n 2 番目のテストケースでは,\u003ci\u003eX\u003c/i\u003e \u003d 1 と設定すると 1 回の戦闘でゲームをクリアできてしまう.\n このケースでは,必要となる戦闘の回数が \u003ci\u003eM\u003c/i\u003e 回以上であり,かつゲームをクリアできるように \u003ci\u003eX\u003c/i\u003e を設定することが出来ない.\n よって -1 のみからなる行を出力する.\n \u003c/p\u003e"}}]}