[USACO Dec07]泥潭

Grade 0 Open Time Friday, 18 January 2013, 9:40 am
Discount 0.8 Time Discount Friday, 18 January 2013, 9:40 am
Allow late Yes Close Time Friday, 18 January 2013, 9:40 am
Input file mud.in Output file mud.out

译 by CmYkRgB123

描述

Farmer John在早晨6点准时去给贝茜挤奶,然而昨天晚上下了大雨,他的牧场变得泥泞不堪了。Farmer John的家在坐标平面的 (0,0) 处,贝茜在 (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)。他看见了所有的 N  (1 ≤ N ≤ 10,000) 个泥潭,分别在 (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) 。每个泥潭只占一个点的位置。

Farmer John 刚刚买了新的靴子,他绝对不想把靴子踩进泥潭弄脏,而他又想尽快的找到贝茜。他已经快晚了,因为他花了大量的时间来找到所有的泥潭的位置。 Farmer John 只能平行于坐标轴移动,每次移动一个单位。请你帮助 Farmer John 找到一条路,使得 Farmer John 能够最快的找到贝茜,而且不会弄脏靴子。我们约定一定存在一条路使 Farmer John 找到贝茜。

输入

* 第 1 行: 三个整数  X, Y, N

* 第 2..N+1 行: 第 i+1 行 包含两个整数 Ai , Bi

输出

* 第 1 行: Farmer John 能够最快的找到贝茜,而且不会弄脏靴子,要走的最小的距离。

样例输入

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2


样例输出

11