Submit　　Ranklist

Problem : 54 - 青蛙子

Problem Statistics

Solved Member: 26　　Submission: 265　　User Tried: 30

Statement:

你家養了一隻青蛙，你知道，養青蛙是一件很麻煩的事情。

跟家裡的寵物建立良好的愛與信賴關係是必備的，例如說，當他偷吃了你後院的植物你就有必要盡主人的義務好好施行愛的教育。

具體一點說，你家的後院是一個R*C的長方形，如下圖是一個6*7的長方形。

你家的青蛙會照著一條由整數點到整數點做等距離的直線跳躍，吃掉每一格它經過的地方，直到它跳出你的後院為止。
你發現來吃你家後院的青蛙或許不只一隻，如下圖，黑點代表被吃掉的作物。你家的青蛙只有可能走其中的一條路線而已。

你和你家的青蛙約反三章，假如他破壞3株以上的稻作就要好好懲罰他！
你是一個明理的主人，你並不會把所有罪過推給你養的青蛙。但是你又希望能夠好好愛她，你現在知道了你後院被摧殘之後的樣子，於是，你決定寫一個程式來計算青蛙子最多會吃掉多少~

Input:Output:

第1行有2個數字，R,C($1 \leq R,C \leq 5000$)，分別代表你後院的寬度和長度。
第2行有1個數字N($3 \leq N \leq 5000$)，代表你後院有幾個格子被摧殘了。
第3行開始的後N行，每行有2個數字$R_i , C_i$ ($1 \leq R_i \leq R$ 且 $1 \leq C_i \leq C$)，代表被摧殘過的稻田座標。

輸出只有一行，請你輸出單一個整數，代表你家青蛙至多吃了多少格的植物。
如果找不到一條滿足的路徑，請輸出0。

Sample Input:Sample Output:

6 7
18
1 1
6 2
3 5
1 5
4 7
1 2
1 4
1 6
1 7
2 1
2 3
2 6
4 2
4 4
4 5
5 4
5 5
6 6

Source:

IOI 2002

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	4
2	1000ms	65536kb	4
3	1000ms	65536kb	4
4	1000ms	65536kb	4
5	1000ms	65536kb	4
6	1000ms	65536kb	4
7	1000ms	65536kb	4
8	1000ms	65536kb	4
9	1000ms	65536kb	4
10	1000ms	65536kb	4
11	1000ms	65536kb	4
12	1000ms	65536kb	4
13	1000ms	65536kb	4
14	1000ms	65536kb	4
15	1000ms	65536kb	4
16	1000ms	65536kb	4
17	1000ms	65536kb	4
18	1000ms	65536kb	4
19	1000ms	65536kb	4
20	1000ms	65536kb	4
21	1000ms	65536kb	4
22	1000ms	65536kb	4
23	1000ms	65536kb	4
24	1000ms	65536kb	4
25	1000ms	65536kb	4