Đề bài

Cuối năm ngoái, Ông già Noel đã quên tặng quà Giáng sinh cho các em nhỏ ở Làng JOI. Vì vậy, để tạ lỗi, ông quyết định giao bánh kem sô-cô-la cho các em nhỏ. Vì ngày giao bánh đã cận kề vào ngày mai, ông phải sớm lên kế hoạch di chuyển.

Làng JOI được chia thành dạng bàn cờ bởi $W$ con đường chạy thẳng theo hướng bắc-nam và $H$ con đường chạy thẳng theo hướng đông-tây. $W$ con đường hướng bắc-nam được đánh số $1, 2, \dots, W$ theo thứ tự từ tây sang đông, và $H$ con đường hướng đông-tây được đánh số $1, 2, \dots, H$ theo thứ tự từ nam lên bắc. Giao điểm nơi con đường hướng bắc-nam thứ $x$ tính từ phía tây và con đường hướng đông-tây thứ $y$ tính từ phía nam cắt nhau được ký hiệu là $(x, y)$. Ở Làng JOI có $N$ ngôi nhà, và mỗi ngôi nhà nằm tại một giao điểm nào đó. Ông già Noel chỉ có thể di chuyển dọc theo các con đường. Thời gian cần thiết để di chuyển giữa hai giao điểm kề nhau là $1$.

Vì tất cả các ngôi nhà ở Làng JOI đều có trẻ em, Ông già Noel phải đi giao bánh kem sô-cô-la cho tất cả các ngôi nhà ở Làng JOI, mỗi nhà $1$ chiếc. Việc cầm những chiếc bánh kem sô-cô-la quý giá bay lượn trên bầu trời cùng tuần lộc là hơi nguy hiểm, nên Ông già Noel và tuần lộc quyết định đáp xuống một giao điểm nào đó ở Làng JOI, và Ông già Noel sẽ đi bộ từ đó để giao bánh kem sô-cô-la. Ông già Noel không bao giờ vừa đi bộ vừa mang cùng lúc từ $2$ chiếc bánh kem sô-cô-la trở lên. Nói cách khác, mỗi lần giao bánh kem sô-cô-la cho $1$ ngôi nhà xong, Ông già Noel đều quay trở lại giao điểm nơi ông đã đáp xuống.

Ông già Noel quyết định chọn một kế hoạch di chuyển sao cho tổng thời gian cần thiết kể từ khi đáp xuống Làng JOI cho đến khi giao xong bánh kem sô-cô-la cho tất cả các ngôi nhà là nhỏ nhất. Lưu ý rằng thời gian quay trở lại giao điểm đáp xuống sau khi đã giao bánh kem sô-cô-la cho ngôi nhà cuối cùng không được tính vào tổng thời gian cần thiết. Ngoài ra, không xét đến bất kỳ yếu tố nào khác ngoài thời gian di chuyển.

Cho thông tin về vị trí của các ngôi nhà, hãy viết chương trình tìm giá trị nhỏ nhất của tổng thời gian cần thiết kể từ khi đáp xuống Làng JOI cho đến khi giao xong bánh kem sô-cô-la cho tất cả các ngôi nhà khi Ông già Noel chọn giao điểm đáp xuống một cách tối ưu, cũng như vị trí của giao điểm cần đáp xuống để tổng thời gian cần thiết là nhỏ nhất.

Dữ liệu vào

Đọc dữ liệu vào sau từ Đầu vào Chuẩn:

• Dòng thứ $1$ chứa các số nguyên $W, H$ cách nhau bởi dấu cách, biểu thị số lượng con đường theo mỗi hướng.
• Dòng thứ $2$ chứa số nguyên $N$, biểu thị số lượng ngôi nhà.
• $N$ dòng tiếp theo chứa thông tin về vị trí của các ngôi nhà. Dòng thứ $(i + 2)$ ($1 \le i \le N$) chứa các số nguyên $X_i, Y_i$ cách nhau bởi dấu cách, biểu thị rằng ngôi nhà thứ $i$ nằm tại giao điểm $(X_i, Y_i)$. Cả $N$ giao điểm này đều đôi một khác nhau.

Dữ liệu ra

In dữ liệu sau ra Đầu ra Chuẩn:

• Dòng thứ $1$ phải chứa $1$ số nguyên biểu thị giá trị nhỏ nhất của tổng thời gian cần thiết.
• Dòng thứ $2$: khi giao điểm cần đáp xuống để tổng thời gian cần thiết nhỏ nhất là $(x, y)$, phải in ra $2$ số nguyên $x, y$ theo thứ tự này, cách nhau bởi dấu cách. Nếu có nhiều giao điểm thích hợp, hãy chọn giao điểm nằm cực tây (tức là có giá trị $x$ nhỏ nhất) trong số đó; nếu vẫn chưa xác định được duy nhất $1$ giao điểm, hãy chọn tiếp giao điểm nằm cực nam (tức là có giá trị $y$ nhỏ nhất) trong số đó.

Ví dụ

Ví dụ 1

Dữ liệu vào

5 4
3
1 1
3 4
5 3

Dữ liệu ra

10
3 3

Giải thích

Chẳng hạn, có thể làm cho tổng thời gian cần thiết đạt nhỏ nhất bằng kế hoạch di chuyển sau:

• Đáp xuống giao điểm $(3, 3)$.
• Giao bánh kem sô-cô-la cho ngôi nhà nằm tại giao điểm $(3, 4)$. Thời gian đã trôi qua tính đến lúc này là $1$.
• Quay lại giao điểm $(3, 3)$. Thời gian đã trôi qua tính đến lúc này là $2$.
• Giao bánh kem sô-cô-la cho ngôi nhà nằm tại giao điểm $(5, 3)$. Thời gian đã trôi qua tính đến lúc này là $4$.
• Quay lại giao điểm $(3, 3)$. Thời gian đã trôi qua tính đến lúc này là $6$.
• Giao bánh kem sô-cô-la cho ngôi nhà nằm tại giao điểm $(1, 1)$. Thời gian đã trôi qua tính đến lúc này là $10$.

Ví dụ 2

Dữ liệu vào

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

Dữ liệu ra

21
2 3

Giải thích

Lưu ý rằng cũng có thể đáp xuống giao điểm nơi có ngôi nhà.

Giới hạn

• $1 \le W \le 1000000000 = 10^9$: số lượng con đường chạy theo hướng bắc-nam.
• $1 \le H \le 1000000000 = 10^9$: số lượng con đường chạy theo hướng đông-tây.
• $1 \le N \le 100000 = 10^5$: số lượng ngôi nhà.
• $1 \le X_i \le W$: số thứ tự con đường hướng bắc-nam tại vị trí ngôi nhà thứ $i$.
• $1 \le Y_i \le H$: số thứ tự con đường hướng đông-tây tại vị trí ngôi nhà thứ $i$.

Lưu ý rằng trong bài toán này, phạm vi của các số nguyên cần xử lý có thể không nằm gọn trong $32$ bit.

Chấm điểm

• Trong các bộ dữ liệu chấm điểm, $40\%$ số điểm thỏa mãn $N \le 1000$.
• Trong các bộ dữ liệu chấm điểm, $10\%$ số điểm thỏa mãn $W \le 50, H \le 50, N \le 1000$.