Junya has just finished her trigonometry test. Her teacher asks her kindly to move the chairs into one stack at some location in the metre classroom. However, her teacher only wants her to move the chairs either along the axis or the axis of the classroom. That is, she is not allowed to move the chair diagonally. Additionally, because she is not that strong, she can only move one chair at a time. For each metre she pushes the chair, it takes her one second.
Being the lazy person she is (but also wanting to be on her teacher's good side), she wants to know the minimum amount of time moving and stacking the chairs will take her.
Help her find the minimum amount of time it will take her to stack all the chairs!
The first line will contain the integer , the number of chairs.
The next lines will each contain two space-separated integers, , the position of the chair. Note that there may be multiple chairs at any one location, in which they are to be treated as independent objects.
Print the minimum amount of time in seconds it will take her to move and stack all the chairs at one location.
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
No further constraints.
Sample Input 1
4 1 1 1 3 1 2 1 10
Sample Output 1
Sample Explanation 1
The best location to stack the chairs would be at .
- It would take the first chair second to move to position .
- It would take the second chair second to move to position .
- It would take the third chair seconds to move to position .
- It would take the last chair seconds to move to position .
Sample Input 2
6 1 1 2 2 3 3 999999998 999999998 999999999 999999999 1000000000 1000000000
Sample Output 2