Để 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 \(n\) vận động viên tham gia. Theo kịch bản, \(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ứ \(i\) đang ở vị trí \((x_i, y_i)\), nếu vận động viên này di chuyển đến vị trí \((u_i, v_i)\) thì sẽ mất năng lượng là \(|x_i - u_i| + |y_i - v_i|\).

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ả \(n\) vận động viên là nhỏ nhất.

Input

• Dòng đầu ghi số nguyên dương \(n\).
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\), các số có giá trị tuyệt đối không vượt quá \(10^9\).

Output

• 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ả \(n\) vận động viên.

Example

3
1 1
1 2
3 3

2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0 \le x_i, y_i \le 100, n \le 11\) và \(n\) là số nguyên tố.
• Subtask \(2\) (\(20\%\) số điểm): \(0 \le x_i, y_i \le 100, n \le 11\).
• Subtask \(3\) (\(20\%\) số điểm): \(0 \le x_i, y_i \le 10000, n < 1000\) và \(n\) là số nguyên tố.
• Subtask \(4\) (\(20\%\) số điểm): \(n < 50000\) và \(n\) là số nguyên tố.
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 50000\).