Problem J: Tree Construction

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.

<image>
Figure 1: An example tree

Write a program that finds a tree connecting all given points with the shortest total length of edges.



Input

The input begins with a line that contains an integer n (1 <= n <= 1000), the number of points. Then n lines follow. The i-th line contains two integers xi and yi (0 <= xi, yi <= 10000), which give the coordinates of the i-th point.

Output

Print the total length of edges in a line.

Examples

Input

5
1 5
2 4
3 3
4 2
5 1


Output

12


Input

1
10000 0


Output

0
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int memo[1024][1024];
int calc(int l, int r, const vector<pair<int,int>> &nodes) {
    if(memo[l][r] >= 0) return memo[l][r];
    if(l+1 == r) return 0;
    pair<int,int> root(min(nodes[l].first, nodes[r-1].first), min(nodes[l].second, nodes[r-1].second));
    memo[l][r] = 10000 * 10000 * 2;
    for(int m = l+1; m < r; ++m) {
        const int d = nodes[m-1].second - root.second + nodes[m].first - root.first;
        memo[l][r] = min(memo[l][r], calc(l, m, nodes) + calc(m, r, nodes) + d);
    }
    return memo[l][r];
}

bool solve() {
    int N;
    if(!(cin >> N)) return false;
    if(!N) return false;

    vector<pair<int,int>> nodes(N);
    for(int i = 0; i < N; ++i) {
        cin >> nodes[i].first >> nodes[i].second;
    }
    for(int i = 0; i <= N; ++i) {
        for(int j = 0; j <= N; ++j) {
            memo[i][j] = -1;
        }
    }
    cout << calc(0, N, nodes) << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while(solve()) ;
    return 0;
}