対空シールド

時は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 行に出力せよ．