Problem Description
Consider a two-dimensional space with a set of points (xi, yi) that satisfy xi < xj and yi > yj for all i < j. We want to have them all connected by a directed tree whose edges go toward either right (x positive) or upward (y positive). The figure below shows an example tree.
Write a program that finds a tree connecting all given points with the shortest total length of edges.
Limits
For all testcases, 0 ≤ Xi, Yi ≤ 109.
Subtask 1 (23%): 1 ≤ N ≤ 50.
Subtask 2 (25%): 1 ≤ N ≤ 500.
Subtask 3 (52%): 1 ≤ N ≤ 5000.
Subtask 4 (0%): Sample Testcases.
Input
The input begins with a line that contains an integer N, the number of points.
Then N lines follow. The i-th line contains two integers X
i and Y
i, which give the coordinates of the i-th point.
Output
Print the total length of edges in a line.
Sample Testcase 1
Input
5
1 5
2 4
3 3
4 2
5 1
Output
12
Sample Testcase 2
Input
1
10000 0
Output
0