Để trình diễn một tiết mục trong màn khai mạc Đại hội thể thao quốc tế, đạo diễn Q đã mời 𝑛 vận động viên tham gia. Theo kịch bản, 𝑛 vận động viên sẽ được xếp thành một khối có dạng hình chữ nhật gồm một số hàng và một số cột. Cụ thể, các vận động viên đứng ở các vị trí có tọa độ nguyên và liên tiếp nhau, xếp thành các hàng song song với trục tọa độ để tạo thành một khối có dạng hình chữ nhật. Hiện tại, vận động viên thứ 𝑖 đang ở vị trí (𝑥𝑖, 𝑦𝑖), nếu vận động viên này di chuyển đến vị trí (𝑢𝑖 , 𝑣𝑖) thì sẽ mất năng lượng là |𝑥𝑖 − 𝑢𝑖 | + |𝑦𝑖 − 𝑣𝑖 |.
Yêu cầu: Hãy giúp đạo diễn xác định cách xếp hàng để tổng năng lượng di chuyển của cả 𝑛 vận động viên là nhỏ nhất.
Dữ liệu:
- Dòng đầu ghi hai số nguyên dương 𝑛;
- Tiếp theo là 𝑛 dòng, dòng thứ 𝑖 chứa hai số nguyên 𝑥𝑖 , 𝑦𝑖 , các số có giá trị tuyệt đối không vượt quá 109.
Kết quả:
Ghi ra một dòng, chứa một số nguyên là tổng năng lượng di chuyển của cả 𝑛 vận động viên.
Input
3
1 1
1 2
3 3
Output
2
Ràng buộc:
- Có 20% số test ứng với 20% số điểm của bài có 0 ≤ 𝑥𝑖 , 𝑦𝑖 ≤ 100; 𝑛 ≤ 11 và 𝑛 là số nguyên tố;
- Có 20% test khác ứng với 20% số điểm của bài có 0 ≤ 𝑥𝑖 , 𝑦𝑖 ≤ 100; 𝑛 ≤ 11;
- Có 20% test khác ứng với 20% số điểm của bài có 0 ≤ 𝑥𝑖 , 𝑦𝑖 ≤ 10000; 𝑛 < 1000 và 𝑛 là số nguyên tố;
- Có 20% test khác ứng với 20% số điểm của bài có 𝑛 < 50000 và 𝑛 là số nguyên tố;
- Có 20% số test còn lại ứng với 20% số điểm của bài có 𝑛 ≤ 50000.
Nguồn: 3D 20162017