TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

57.7% (45/78)

Tags

Description

當你不費吹灰之力的過完了第一關後,沒想到又馬上來了一個『砲打皮皮2』,遊戲規則跟『砲打皮皮』一樣,只不過你上次那把槍耐力值用完了,但是你有了個新道具『強者炸彈』,這顆炸彈可以依照放入的強者物質的多寡調整其爆炸半徑,每放入一單位強者物質,爆炸半徑就會多一單位,現在你擁有k單位的強者物質,你有辦法消滅棋盤上所有的皮皮嗎?

Input Format

輸入可能包含多筆測試資料。
每筆測試資料的第一行有兩個正整數 N, M(1 ≦ N ≦ 1,000,3 ≦ M ≦ N2 )分別代表棋盤的大小和皮皮的個數。
接下來有 M 行,每行有兩個正整數 X, Y,代表皮皮所在的座標(0 ≦ X, Y ≦ N)。
不會有兩個皮皮在同樣的位子上。
當N = M = 0時,代表輸入結束,聰明的你當然不會對它輸出任何資料。

Output Format

請輸出最少需要多少單位的強者物質,無條件進位到整數位。

Sample Input 1

5 4
0 0
0 1
1 1
1 0
3 3
1 1
2 2
2 3
2 6
0 0
0 2
1 1
1 2
2 0
2 2
4 7
0 0
1 1
2 2
3 4
4 2
0 3
3 0
0 0

Sample Output 1

1
2
2
3

Hints

Problem Source

原TIOJ1254 / INFOR 21st幹部考(prob J)。Problem Setter:peter50216。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10