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<stdio.h>
#include<algorithm>
using namespace std;
int dp[1100][1100];
int v[1100][1100];
int x[1100];
int y[1100];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i);
	for(int i=0;i<a;i++){
		dp[i][i]=0;v[i][i]=i;
	}
	for(int i=1;i<a;i++){
		for(int j=0;i+j<a;j++){
			int now=999999999;
			for(int k=v[j][j+i-1];k<=v[j+1][j+i];k++){
			//	if(k==a-1)continue;
				if(k<j||k>=j+i)continue;
				int cost=dp[j][k]+dp[k+1][j+i]+y[k]-y[i+j]+x[k+1]-x[j];
			//	printf("%d %d %d %d\n",y[k],y[i+j],x[k+1],x[j]);
				if(now>cost){
					v[j][j+i]=k;
					now=cost;
				}
			}
			dp[j][j+i]=now;
		//	printf("%d %d: %d %d\n",j,j+i,now,v[j][j+i]);
		}
	}
	printf("%d\n",dp[0][a-1]);
}