GlobeX Cup '18 S Sample - Chair Stacking

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Junya has just finished her trigonometry test. Her teacher asks her kindly to move the chairs into one stack at some location in the 10^9 \times 10^9 metre classroom. However, her teacher only wants her to move the chairs either along the x axis or the y 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!

Input Specification

The first line will contain the integer N\ (2 \le N \le 10^5), the number of chairs.

The next N lines will each contain two space-separated integers, x_i, y_i\ (1 \le x_i, y_i \le 10^9), the position of the i^{th} chair. Note that there may be multiple chairs at any one location, in which they are to be treated as independent objects.

Output Specification

Print the minimum amount of time in seconds it will take her to move and stack all the chairs at one location.

Subtasks

Subtask 1 [10%]

N \le 100, x_i, y_i \le 100

Subtask 2 [30%]

x_i = 1

Subtask 3 [60%]

No further constraints.

Sample Input 1

4
1 1
1 3
1 2
1 10

Sample Output 1

10

Sample Explanation 1

The best location to stack the chairs would be at (1, 2).

  • It would take the first chair 1 second to move to position (1, 2).
  • It would take the second chair 1 second to move to position (1, 2).
  • It would take the third chair 0 seconds to move to position (1, 2).
  • It would take the last chair 8 seconds to move to position (1, 2).

Sample Input 2

6
1 1
2 2
3 3
999999998 999999998
999999999 999999999
1000000000 1000000000

Sample Output 2

5999999982

Comments

There are no comments at the moment.