问题 1984. -- 楼兰宝藏

1984: 楼兰宝藏

时间限制: 1 Sec  内存限制: 128 MB
提交: 24  解决: 10
[提交][状态][讨论版]

题目描述

在魔法世界的历史上,楼兰是个充满了神秘色彩的名字。那座昔日绿草遍地人往如织的繁荣古城──楼兰,在公元4 世纪以后,却突然神秘地消失了,留下的只是 “城郭巍然,人物断绝”的不毛之地和难解之谜。

不过著名冒险家席慕蓉在一次探险中发现,原来被沙丘掩埋的楼兰古国地下,埋藏着不计其数的宝藏。

简单说来,就是在一张 N×M的地图,地图上画有P个宝藏(1 ≤ N,M ≤1000000000,P ≤100000),每次当探险者坐标为 (x,y)时,他可以向 (x+1,y)或 (x,y+1)移动一格,问最少要多少次才能拣起所有的宝藏(每次走到最后一步时,会自动传送回左上角位置)。

输入

第一行有三个整数,分别为N,M,P。余下P行分别为每个宝藏的X、Y坐标。

输出

一个整数,即次数。

样例输入

7 7 7
1 2
1 4
2 4
2 6
4 4
4 7
6 6

样例输出

2

提示

来源

[提交][状态]