문제 설명

작년 말, 산타클로스는 JOI 마을의 아이들에게 크리스마스 선물을 주는 것을 잊어버렸다. 그래서 사과의 마음으로 아이들에게 초콜릿 케이크를 배달하기로 했다. 배달해야 할 날이 내일로 다가왔기 때문에, 이제 슬슬 이동 계획을 생각해야 한다.

JOI 마을은 남북 방향으로 곧게 뻗은 $W$개의 도로와 동서 방향으로 곧게 뻗은 $H$개의 도로에 의해 바둑판 모양으로 구획되어 있다. 남북 방향의 $W$개의 도로에는 서쪽에서부터 순서대로 $1, 2, \dots, W$의 번호가 매겨져 있으며, 동서 방향의 $H$개의 도로에는 남쪽에서부터 순서대로 $1, 2, \dots, H$의 번호가 매겨져 있다. 서쪽에서 $x$번째인 남북 방향 도로와 남쪽에서 $y$번째인 동서 방향 도로가 만나는 교차점을 $(x, y)$로 나타낸다. JOI 마을에는 $N$채의 집이 있으며, 각 집은 어느 한 교차점에 위치해 있다. 산타클로스는 도로를 따라서만 이동할 수 있다. 인접한 교차점 사이를 이동하는 데 걸리는 시간을 $1$이라 한다.

JOI 마을의 모든 집에는 아이가 있기 때문에, 산타클로스는 JOI 마을의 모든 집에 $1$개씩 초콜릿 케이크를 배달하며 돌아야 한다. 소중한 초콜릿 케이크를 들고 순록과 함께 하늘을 날아다니는 것은 다소 위험하므로, 산타클로스와 순록은 JOI 마을의 어느 한 교차점에 내려앉고, 산타클로스가 거기서부터 걸어서 초콜릿 케이크를 배달하기로 했다. 산타클로스는 동시에 $2$개 이상의 초콜릿 케이크를 들고 걷지 않는다. 즉, 산타클로스는 초콜릿 케이크를 $1$채의 집에 배달할 때마다 내려앉은 교차점으로 돌아온다.

산타클로스는 JOI 마을에 내려앉은 후부터 모든 집에 초콜릿 케이크를 배달할 때까지의 소요 시간이 최소가 되도록 이동 계획을 선택하기로 했다. 여기서, 마지막 집에 초콜릿 케이크를 배달한 후 내려앉은 교차점으로 돌아올 때까지의 시간은 소요 시간에 포함하지 않는다는 점에 주의하라. 또한, 이동에 걸리는 시간 이외에는 고려하지 않는다.

집들의 위치 정보가 주어졌을 때, 산타클로스가 내려앉을 교차점을 잘 선택했을 경우 JOI 마을에 내려앉은 후부터 모든 집에 초콜릿 케이크를 배달할 때까지의 소요 시간의 최솟값과, 소요 시간을 최소로 하기 위해 내려앉아야 할 교차점의 위치를 구하는 프로그램을 작성하시오.

입력

표준 입력에서 다음 입력을 읽어 들이시오.

• $1$번째 줄에는 각 방향의 도로의 개수를 나타내는 정수 $W, H$가 공백으로 구분되어 적혀 있다.
• $2$번째 줄에는 집의 수를 나타내는 정수 $N$이 적혀 있다.
• 이어지는 $N$개의 줄에는 집의 위치 정보가 적혀 있다. $(i + 2)$번째 줄($1 \le i \le N$)에는 정수 $X_i, Y_i$가 공백으로 구분되어 적혀 있으며, $i$번째 집이 교차점 $(X_i, Y_i)$에 위치해 있음을 나타낸다. 이 $N$개의 교차점은 모두 서로 다르다.

출력

표준 출력에 다음 데이터를 출력하시오.

• $1$번째 줄에는 소요 시간의 최솟값을 나타내는 $1$개의 정수가 적혀 있어야 한다.
• $2$번째 줄에는 소요 시간을 최소로 하기 위해 내려앉아야 할 교차점이 $(x, y)$일 때, $2$개의 정수 $x, y$가 이 순서대로 공백으로 구분되어 적혀 있어야 한다. 적절한 교차점이 여러 개 있는 경우에는 그중 가장 서쪽에 있는(즉, $x$의 값이 작은) 교차점을, 그래도 $1$개로 정해지지 않는 경우에는 그중에서 가장 남쪽에 있는(즉, $y$의 값이 작은) 교차점을 선택하라.

예제

예제 1

입력

5 4
3
1 1
3 4
5 3

출력

10
3 3

설명

예를 들어, 다음과 같은 이동 계획에 의해 소요 시간을 최소로 할 수 있다.

• 교차점 $(3, 3)$에 내려앉는다.
• 교차점 $(3, 4)$에 위치해 있는 집에 초콜릿 케이크를 배달한다. 여기까지의 경과 시간은 $1$이다.
• 교차점 $(3, 3)$으로 돌아온다. 여기까지의 경과 시간은 $2$이다.
• 교차점 $(5, 3)$에 위치해 있는 집에 초콜릿 케이크를 배달한다. 여기까지의 경과 시간은 $4$이다.
• 교차점 $(3, 3)$으로 돌아온다. 여기까지의 경과 시간은 $6$이다.
• 교차점 $(1, 1)$에 위치해 있는 집에 초콜릿 케이크를 배달한다. 여기까지의 경과 시간은 $10$이다.

예제 2

입력

4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

출력

21
2 3

설명

집이 있는 교차점에 내려앉아도 된다는 점에 주의하라.

제약 조건

• $1 \le W \le 1000000000 = 10^9$: 남북 방향으로 뻗은 도로의 개수.
• $1 \le H \le 1000000000 = 10^9$: 동서 방향으로 뻗은 도로의 개수.
• $1 \le N \le 100000 = 10^5$: 집의 수.
• $1 \le X_i \le W$: $i$번째 집의 위치의, 남북 방향으로 뻗은 도로의 번호.
• $1 \le Y_i \le H$: $i$번째 집의 위치의, 동서 방향으로 뻗은 도로의 번호.

이 문제에서는 다루는 정수의 범위가 $32$비트에 들어가지 않을 가능성이 있다는 점에 주의하라.

채점 기준

• 채점용 데이터 중 배점의 $40\%$ 분량에 대해서는 $N \le 1000$을 만족한다.
• 채점용 데이터 중 배점의 $10\%$ 분량에 대해서는 $W \le 50, H \le 50, N \le 1000$을 만족한다.