対空シールド
시간 제한8초메모리 제한512 MB
M-1개의 위치가 정해진 실드와 아직 배치하지 않은 실드 하나가 주어질 때, 마지막 실드의 위치를 정해 N개 유닛 강도의 최솟값을 최대화하고 그 값을 구한다.
문제
時は3xxx年，太陽系外の惑星に進出した人類は，大量の隕石の飛来による基地の被害で頭を悩ませていた．国際宇宙防護会社（International Cosmic Protection Company）は，この問題を解決するために新たな対空シールドを開発した．
防護対象の基地は同じサイズの N 個のユニットが一直線上に等間隔で並んだ形をしており， 1 から N までの番号が順に付けられている．ICPCは，これらのユニットに，合計で M 個のシールドを設置することにした．i 番目のシールドが能力 ai を持ち，ユニット xi に設置されているとする．このとき，あるユニット u における強度は，以下の式で表される．
Σi=1M max(ai-(u-xi)2,0)
シールドはユニットにのみ設置することができ，複数のシールドを同じユニットに設置することもできる．そして，ICPCに支払われる報酬は N 個のユニットの強度の最小値に比例した額となる．
シールドの能力は全て既に決まっており，位置も最後の 1 つ以外は決定している．最後の 1 つのシールドの位置を決めるにあたって，報酬がなるべく大きくなるようにしたい．このように最後のシールドの位置を決めたときの強度の最小値を求めよ．
입력
入力は最大で 30 個のデータセットからなる．各データセットは次の形式で表される．
N M
a1 x1
…
aM-1 xM-1
aM
N はユニットの個数，M はシールドの個数を表す．N と M は整数であり，1 ≤ N ≤ 106，1 ≤ M ≤ 105を満たす．続く M 行には各シールドの情報が与えられる．ai と xi はそれぞれシールドの能力と位置を表す整数であり，1 ≤ ai ≤ 109，1 ≤ xi ≤ N を満たす．M 番目のシールドの位置はまだ決定していないため，入力で与えられないことに注意せよ．
入力の終わりは 2 つのゼロからなる行で表される．
출력
各データセットについて，M 番目のシールドの設置位置を適切に決めたときの，強度の最小値を 1 行に出力せよ．