기념물 투어

여행사가 파리의 기념물과 박물관 N곳을 방문하는 일정을 제안한다. 도시는 격자로 모델링된다. 투어는 다음과 같이 진행된다. 버스는 서쪽에서 도시로 진입하고(어느 거리로든 진입 가능), 도시를 가로지르며 기념물을 방문할 필요가 있을 때 좌회전 또는 우회전하여 방문한 뒤, 진입할 때 사용한 동쪽 방향 도로로 돌아온다. 이 과정을 반복하다가 동쪽으로 도시를 빠져나간다.

6 × 5 격자 도시에서의 투어는 위 그림과 같을 수 있다. 그림에서 버스는 좌표 (0, 2)로 도시에 진입하고((0, 0)을 도시의 북서쪽 모서리로 본다), 먼저 (1, 2)에 있는 기념물을 방문한 뒤(이미 주요 도로 위에 있다), 좌회전하여 (1, 0)에 있는 기념물을 방문하고, 주요 도로로 돌아와 동쪽으로 이동하다가 우회전하여 (2, 4)에 있는 기념물을 방문하고, 주요 도로로 돌아와 (4, 2)에 있는 기념물을 방문한 뒤(역시 주요 도로 위에 있다), 좌표 (5, 2)에서 도시를 빠져나간다. 버스 운행사는 한 블록을 지날 때마다 1단위의 연료가 든다고 계산한다. 위 예시의 비용은 5 + 2 × 2 + 2 × 2 = 13단위의 연료이다.

당신의 임무는 여행사가 버스로 이동할 동쪽 방향 도로를 선택하도록 도와, N곳의 기념물을 모두 방문하면서 투어 비용을 최소로 만드는 것이다.

입력은 여러 줄로 이루어지며, 각 줄은 단일 공백으로 구분된 정수로 구성된다.

• 첫째 줄에는 북쪽 방향 거리의 수 X와 동쪽 방향 거리의 수 Y가 주어진다.
• 둘째 줄에는 투어가 방문해야 하는 기념물의 수 N이 주어진다.
• 다음 N개 줄에는 각 기념물의 좌표 xi와 yi가 주어진다.

출력은 한 줄로 이루어지며, 투어의 최소 비용을 나타내는 정수를 출력한다.

• 1 ≤ X, Y ≤ 100 000
• 1 ≤ N ≤ 100 000
• 0 ≤ xi < X, 0 ≤ yi < Y

• 버스 운행사는 다른 평행한 동쪽 방향 도로로 돌아갈 수 없다. 도시에 진입할 때 사용한 도로와 같은 도로를 사용해야 한다.
• 같은 좌표에 둘 이상의 기념물이 있을 수 있다.