Many years have passed, and n friends met at a party again. Technologies have leaped forward since the last meeting, cameras with timer appeared and now it is not obligatory for one of the friends to stand with a camera, and, thus, being absent on the photo.

Simply speaking, the process of photographing can be described as follows. Each friend occupies a rectangle of pixels on the photo: the i-th of them in a standing state occupies a wi pixels wide and a hi pixels high rectangle. But also, each person can lie down for the photo, and then he will occupy a hi pixels wide and a wi pixels high rectangle.

The total photo will have size W × H, where W is the total width of all the people rectangles, and H is the maximum of the heights. The friends want to determine what minimum area the group photo can they obtain if no more than n / 2 of them can lie on the ground (it would be strange if more than n / 2 gentlemen lie on the ground together, isn't it?..)

Help them to achieve this goal.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of friends.

The next n lines have two integers wi, hi (1 ≤ wi, hi ≤ 1000) each, representing the size of the rectangle, corresponding to the i-th friend.

Output

Print a single integer equal to the minimum possible area of the photo containing all friends if no more than n / 2 of them can lie on the ground.

Examples

Input

3
10 1
20 2
30 3


Output

180


Input

3
3 1
2 2
4 3


Output

21


Input

1
5 10


Output

50
import java.util.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;



public class Main{
	
	// ArrayList<Integer> lis = new ArrayList<Integer>();
	// ArrayList<String> lis = new ArrayList<String>();
	// PriorityQueue<P> que = new PriorityQueue<P>();
	// PriorityQueue<Integer> que = new PriorityQueue<Integer>();
	//  Stack<Integer> que = new Stack<Integer>();
	//HashMap<Long,Long> map = new HashMap<Long,Long>();
    //	static long sum=0;
	// 1000000007 (10^9+7)
	//static int mod = 1000000007;
	static long mod = 1000000007;
	//static int mod = 1000000009; ArrayList<Integer> l[]= new ArrayList[n];
    static int dx[]={1,-1,0,0};
	static int dy[]={0,0,1,-1};
	//static int dx[]={1,-1,0,0,1,1,-1,-1};
    //static int dy[]={0,0,1,-1,1,-1,1,-1};
	
	//static Set<Integer> set = new HashSet<Integer>();
	//static ArrayList<Integer> l[];
    //static int parent[][],depth[],node,max_log;
	//static ArrayList<Integer> l[];
    

public  static void main(String[] args)   throws Exception, IOException{

	//Scanner sc =new Scanner(System.in);
	
	Reader sc = new Reader(System.in);
   

	//int a=sc.nextInt(),b=sc.nextInt(),c=sc.nextInt();
	int n=sc.nextInt();//,c=sc.nextInt();//,m=sc.nextInt();//,k=sc.nextInt(),s=0;
    int r=Integer.MAX_VALUE,k=n/2;

    int d[][]=new int[2][n];
    for (int i = 0; i < n; i++) {
    	d[0][i]=sc.nextInt();
    	d[1][i]=sc.nextInt();
	}
    lp:
    for (int i = 1; i <= 1000; i++) {
		int x=0,c=0;
		ArrayList<Integer> l=new ArrayList<Integer>();
		
		
    	for (int j = 0; j < n; j++) {
		  if(d[1][j]>i){ if(d[0][j]>i)continue lp; x+=d[1][j]; c++; }
		  else {
			  if( d[0][j]>i )x+=d[0][j];
			  else {  l.add(-(abs(d[0][j]-d[1][j])*1000+j)) ; }
		  }
		}
    	
    	if(c>k)continue;
    	c=k-c;
    	sort(l);
    	
    	for (int j = 0; j < l.size(); j++) {
    		int id=-l.get(j)%1000;
			if(c>0){ 
				if(d[0][id]<=d[1][id])x+=d[0][id];
				else {x+=d[1][id]; c--;} }
			else x+=d[0][id];
    		
		}
    	
    	r=min(r,x*i);
    	
	}
	
	
	System.out.println(r);

}



/*
  static class P implements Comparable<P>{
	int id, d; ;
	P(int id,int d){
		this.id=id;
		this.d=d;
	} 
	
	public int compareTo(P x){
	//	return  (-x.d+d)>=0?1:-1  ; // ascend long
	//	return   -x.d+d  ; // ascend
		 return   x.d-d  ; //descend
	   }
 
}//*/



static void db(Object... os){
    System.err.println(Arrays.deepToString(os));

}

static boolean validpos(int x,int y,int r, int c){
	
	return x<r && 0<=x && y<c && 0<=y;
	
}

static boolean bit(int x,int k){
	// weather k-th bit (from right) be one or zero
	return  ( 0 < ( (x>>k) & 1 )  )  ? true:false;
}

}


class bit { // 1base!

	 int b[],n;
	 
	 bit(int n){
		 this.n=n;
		 b=new int[n+1];
	 }
	 
	int sum(int i){
		int s=0;
		while(i>0){
			s+=b[i];
			i -= i&-i;
		}
	return s;	
	}
	
	void add(int i,int x){
		while(i<=n){
			b[i]+=x;
			i += i&-i;
		}	
	}
	
}

class Reader
{ 
	private BufferedReader x;
	private StringTokenizer st;
	
	public Reader(InputStream in)
	{
		x = new BufferedReader(new InputStreamReader(in));
		st = null;
	}
	public String nextString() throws IOException
	{
		while( st==null || !st.hasMoreTokens() )
			st = new StringTokenizer(x.readLine());
		return st.nextToken();
	}
	public int nextInt() throws IOException
	{
		return Integer.parseInt(nextString());
	}
	public long nextLong() throws IOException
	{
		return Long.parseLong(nextString());
	}
	public double nextDouble() throws IOException
	{
		return Double.parseDouble(nextString());
	}
}