対空シールド

時は3xxx年，太陽系外の惑星に進出した人類は，大量の隕石の飛来による基地の被害で頭を悩ませていた．国際宇宙防護会社（International Cosmic Protection Company）は，この問題を解決するために新たな対空シールドを開発した．

防護対象の基地は同じサイズの N 個のユニットが一直線上に等間隔で並んだ形をしており， 1 から N までの番号が順に付けられている．ICPCは，これらのユニットに，合計で M 個のシールドを設置することにした．i 番目のシールドが能力 a_i を持ち，ユニット x_i に設置されているとする．このとき，あるユニット u における強度は，以下の式で表される．

Σ_i=1^M max(a_i-(u-x_i)²,0)

シールドはユニットにのみ設置することができ，複数のシールドを同じユニットに設置することもできる．そして，ICPCに支払われる報酬は N 個のユニットの強度の最小値に比例した額となる．

シールドの能力は全て既に決まっており，位置も最後の 1 つ以外は決定している．最後の 1 つのシールドの位置を決めるにあたって，報酬がなるべく大きくなるようにしたい．このように最後のシールドの位置を決めたときの強度の最小値を求めよ．

Input

入力は最大で 30 個のデータセットからなる．各データセットは次の形式で表される．

N M a₁ x₁ … a_M-1 x_M-1 a_M

N はユニットの個数，M はシールドの個数を表す．N と M は整数であり，1 ≤ N ≤ 10⁶，1 ≤ M ≤ 10⁵を満たす．続く M 行には各シールドの情報が与えられる．a_i と x_i はそれぞれシールドの能力と位置を表す整数であり，1 ≤ a_i ≤ 10⁹，1 ≤ x_i ≤ N を満たす．M 番目のシールドの位置はまだ決定していないため，入力で与えられないことに注意せよ．

入力の終わりは 2 つのゼロからなる行で表される．

Output

各データセットについて，M 番目のシールドの設置位置を適切に決めたときの，強度の最小値を 1 行に出力せよ．

Sample Input

3 3
2 1
2 2
10
10 4
1 1
1 5
1 9
1
5 7
1000000000 1
1000000000 1
1000000000 3
1000000000 3
1000000000 5
1000000000 5
1
10000 11
10934235 560
3155907 1508
10901182 2457
3471816 3590
10087848 4417
16876957 5583
23145027 6540
15162205 7454
1749653 8481
6216466 9554
7198514
701 14
8181 636
4942 273
1706 282
6758 20
7139 148
6055 629
8765 369
5487 95
6111 77
2302 419
9974 699
108 444
1136 495
2443
0 0

Output for the Sample Input

10
0
5999999960
23574372
985