Brave Force Story

Time Limit : 8 sec, Memory Limit : 65536 KB

ブレイブ・フォース・ストーリー

English text is not available in this practice contest.

「最果ての地,ナイン・アイランドには特別な力を持つものが生きていた. ある者は火,ある者は氷,ある者は風,ある者は土を意のままに操ることができた. 人はこれらの術者をこう呼んだ.『Brave Force』と・・・.時は戦国時代.権力者たちはBrave Forceを私欲のために使わんとBrave Force狩りを始めた. Brave Forceを巡る戦いが今始まろうとしている.」

以上は,あなたが今つくろうとしている戦略シミュレーションゲームのプロローグである.このプロローグは本問題には全く関係ない.

問題の説明に戻ろう.戦略シミュレーションの世界においては, 正6角形のマスがよく使われる. これは, 正方形のマスに比べて方向による距離の違いが小さく, 敷き詰めも可能であるからである.

今回はこのようなマップ上でコマを動かすことを考える.コマは各ターンごとに隣接するマスに移動させることができる. もちろんマップ上には多くの障害物があってそこには移動することができない.さて一定のターン数が経過するまでにたどり着くことが可能なマスの数はいくつあるだろうか.

Input

入力はそれぞれがマップの情報を表す1つ以上のデータセットからなる.

データセットの最初の行には, 2つの整数が含まれていて, 1番目がターン数 t で, 2番目が障害物の数 n である.

それに続く n 行にはそれぞれ障害物のマスの座標を表す2つの整数が含まれていて, 1番目が x 座標で, 2番目が y 座標である. 障害物の座標は互いに異なっている.

そして最後の行にはスタート位置のマスの座標を表す2つの整数が含まれていて, 1番目が x 座標で, 2番目が y 座標である. このマスには障害物はない. またこのマスは到達できるマスに含められる.

マスに割り当てられた座標は下の図のようになっている.


図B-1 マスに割り当てられた座標

入力の終わりは"0 0"を含む行で表される.

いずれの座標も絶対値が30以下である. ターン数は1以上30以下である. 障害物の数は0以上300以下である.


図B-2 Sample Input の1つ目のデータセット

Output

各マップについて到達できるマスの数を表す整数を各行に出力せよ. それ以外の余計な文字を出力に含めてはいけない.

Sample Input

1 1
1 0
0 0
2 2
-2 1
2 0
2 2
2 0
-1 1
4 4
-2 1
1 -2
1 2
3 -3
-2 0
4 6
0 1
1 1
1 0
-1 0
-1 -1
0 -1
0 0
0 0

Output for the Sample Input

6
18
19
58
1

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2011, 2011-06-12
http://acm-icpc.aitea.net/