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. Để xin lỗi, ông quyết định mang bánh sô-cô-la đến cho các em. Ngày giao bánh đã là ngày mai, nên ông cần sớm lập kế hoạch di chuyển.

Làng JOI được chia thành một lưới ô vuông bởi \(W\) con đường thẳng theo hướng bắc–nam và \(H\) con đường thẳng theo hướng đông–tây. Các con đường bắc–nam được đánh số \(1,2,\ldots,W\) từ tây sang đông; các con đường đông–tây được đánh số \(1,2,\ldots,H\) từ nam lên bắc. Giao điểm của con đường bắc–nam thứ \(x\) tính từ phía tây và con đường đông–tây thứ \(y\) tính từ phía nam được ký hiệu là \((x,y)\).

Trong làng có \(N\) ngôi nhà, mỗi ngôi nhà nằm tại một giao điểm. Ông già Noel chỉ được di chuyển dọc theo các con đường. Thời gian đi giữa hai giao điểm kề nhau là \(1\).

Mọi ngôi nhà trong làng đều có trẻ em, nên ông già Noel phải giao đúng một chiếc bánh sô-cô-la đến mỗi nhà. Mang những chiếc bánh quý giá bay trên trời cùng tuần lộc có phần nguy hiểm, nên ông và tuần lộc sẽ hạ cánh tại một giao điểm trong làng, rồi ông đi bộ từ đó để giao bánh. Ông không đi bộ mang theo từ hai chiếc bánh trở lên cùng lúc. Vì vậy, sau mỗi lần giao bánh cho một nhà, ông quay về giao điểm đã hạ cánh.

Ông già Noel muốn chọn kế hoạch có tổng thời gian từ lúc hạ cánh đến khi giao xong bánh cho tất cả các nhà là nhỏ nhất. Lưu ý rằng thời gian quay về giao điểm hạ cánh sau khi giao bánh cho ngôi nhà cuối cùng không được tính vào tổng thời gian. Chỉ tính thời gian di chuyển, bỏ qua mọi thời gian khác.

Yêu cầu

Cho vị trí các ngôi nhà, hãy viết chương trình tìm tổng thời gian nhỏ nhất nếu chọn giao điểm hạ cánh tối ưu, đồng thời tìm vị trí giao điểm cần hạ cánh để đạt được tổng thời gian đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

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

Dữ liệu ra

Ghi ra đầu ra chuẩn:

• Dòng đầu tiên chứa một số nguyên là tổng thời gian nhỏ nhất.
• Dòng thứ hai chứa hai số nguyên \(x,y\) theo thứ tự đó, cách nhau bởi dấu cách, là tọa độ giao điểm hạ cánh để đạt được tổng thời gian nhỏ nhất. Nếu có nhiều giao điểm phù hợp, chọn giao điểm ở xa nhất về phía tây, tức có \(x\) nhỏ nhất. Nếu vẫn còn nhiều lựa chọn, chọn giao điểm ở xa nhất về phía nam trong số đó, tức có \(y\) nhỏ nhất.

Ràng buộc

• \(1\le W\le1000000000=10^9\).
• \(1\le H\le1000000000=10^9\).
• \(1\le N\le100000=10^5\).
• \(1\le X_i\le W\) và \(1\le Y_i\le H\) với mọi \(1\le i\le N\).
• Các cặp \((X_i,Y_i)\) đôi một khác nhau.
• Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

Lưu ý

Các số nguyên cần xử lý trong bài này có thể vượt quá phạm vi biểu diễn của kiểu số nguyên \(32\) bit.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(20\) nhóm dữ liệu, mỗi nhóm \(5\) điểm. Mỗi nhóm gồm nhiều bộ dữ liệu; chỉ nhận được điểm của nhóm nếu trả lời đúng tất cả các bộ dữ liệu trong nhóm đó. Các điều kiện điểm thành phần dưới đây có thể chồng lấp:

• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(N\le1000\).
• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(W\le50\), \(H\le50\) và \(N\le1000\).

Ví dụ

5 4
3
1 1
3 4
5 3

10
3 3

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

21
2 3