Snuke received N intervals as a birthday present. The i-th interval was [-L_i, R_i]. It is guaranteed that both L_i and R_i are positive. In other words, the origin is strictly inside each interval.

Snuke doesn't like overlapping intervals, so he decided to move some intervals. For any positive integer d, if he pays d dollars, he can choose one of the intervals and move it by the distance of d. That is, if the chosen segment is [a, b], he can change it to either [a+d, b+d] or [a-d, b-d].

He can repeat this type of operation arbitrary number of times. After the operations, the intervals must be pairwise disjoint (however, they may touch at a point). Formally, for any two intervals, the length of the intersection must be zero.

Compute the minimum cost required to achieve his goal.

Constraints

* 1 ≤ N ≤ 5000
* 1 ≤ L_i, R_i ≤ 10^9
* All values in the input are integers.

Input

The input is given from Standard Input in the following format:


N
L_1 R_1
:
L_N R_N


Output

Print the minimum cost required to achieve his goal.

Examples

Input

4
2 7
2 5
4 1
7 5


Output

22


Input

20
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80
57 18
34 28
76 55
21 80


Output

7337
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<utility>
#include<functional>
#include<iomanip>
#include<sstream>
#include<ctime>
#include<cassert>
using namespace std;
#define y0 y0z
#define y1 y1z
#define yn ynz
#define j0 j0z
#define j1 j1z
#define jn jnz
#define tm tmz
#define buli(x) (__builtin_popcountll(x))
#define bur0(x) (__builtin_ctzll(x))
#define bul2(x) (63-__builtin_clzll(x))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fil(a,b) memset((a),(b),sizeof(a))
#define cl(a) fil(a,0)
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)
#define rep(i,a,b) for (int i=(a),_ed=(b);i<_ed;i++)
#define per(i,a,b) for (int i=(b)-1,_ed=(a);i>=_ed;i--)
#define forg(i,gu) for (int i=gu;~i;i=e[i].next)
#define pw(x) ((ll(1))<<(x))
#define upmo(a,b) (((a)=((a)+(b))%mo)<0?(a)+=mo:(a))
#define mmo(a,b) (((a)=1ll*(a)*(b)%mo)<0?(a)+=mo:(a))
void getre(){int x=0;printf("%d\n",1/x);}
void gettle(){int res=1;while(1)res<<=1;printf("%d\n",res);}
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename N,typename PN>inline N flo(N a,PN b){return a>=0?a/b:-((-a-1)/b)-1;}
template<typename N,typename PN>inline N cei(N a,PN b){return a>0?(a-1)/b+1:-(-a/b);}
template<typename N>N gcd(N a,N b){return b?gcd(b,a%b):a;}
template<typename N>inline int sgn(N a){return a>0?1:(a<0?-1:0);}
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
inline void gn(long long&x){
	int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');c=='-'?(sg=-1,x=0):(x=c-'0');
	while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=sg;
}
inline void gn(int&x){long long t;gn(t);x=t;}
inline void gn(unsigned long long&x){long long t;gn(t);x=t;}
inline void gn(double&x){double t;scanf("%lf",&t);x=t;}
inline void gn(long double&x){double t;scanf("%lf",&t);x=t;}
inline void gs(char *s){scanf("%s",s);}
inline void gc(char &c){while((c=getchar())>126 || c<33);}
inline void pc(char c){putchar(c);}
#ifdef JCVB
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
typedef long long ll;
typedef double db;
inline ll sqr(ll a){return a*a;}
inline db sqrf(db a){return a*a;}
const int inf=0x3f3f3f3f;
const db pi=3.14159265358979323846264338327950288L;
const db eps=1e-6;
//const int mo=0;
//int qp(int a,ll b){int n=1;do{if(b&1)n=1ll*n*a%mo;a=1ll*a*a%mo;}while(b>>=1);return n;}

struct node{
	int l,r;
	void read(){
		gn(l);gn(r);
	}
}a[5555];
int cmp(const node&a,const node&b){
	return a.r+a.l>b.r+b.l;
}


ll f[2][5055][2];
int n;
int main()
{
#ifdef JCVB
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int _time_jc=clock();
#endif
	gn(n);
	rep(i,1,n+1){
		a[i].read();
	}
	fil(f[0],63);
	f[0][0][0]=0;
	sort(a+1,a+1+n,cmp);

	ll ans=0x3f3f3f3f3f3f3f3fll;
	for (int d=0;d<n;d++){
		fil(f[(d&1)^1],63);
		rep(l,0,d+1){
			int r=d-l;
			upmin(f[(d&1)^1][l][0],f[d&1][l][0]+a[d+1].l+1ll*r*(a[d+1].r+a[d+1].l));
			upmin(f[(d&1)^1][l+1][0],f[d&1][l][0]+a[d+1].r+1ll*l*(a[d+1].r+a[d+1].l));

			upmin(f[(d&1)^1][l][1],f[d&1][l][0]+1ll*(n/2)*(a[d+1].r+a[d+1].l));

			if(d-l-1>=0){
				r=d-l-1;
				upmin(f[(d&1)^1][l][1],f[d&1][l][1]+a[d+1].l+1ll*r*(a[d+1].r+a[d+1].l));
				upmin(f[(d&1)^1][l+1][1],f[d&1][l][1]+a[d+1].r+1ll*l*(a[d+1].r+a[d+1].l));
			}
		}
	}

	rep(i,0,n+1){
		upmin(ans,f[n&1][i][0]);
	}
	if(n%2==1){
		upmin(ans,f[n&1][n/2][1]);
	}

	cout<<ans<<endl;

#ifdef JCVB
	debug("time: %d\n",int(clock()-_time_jc));
#endif
	return 0;
}


