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.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;


public class GroupPhoto2 {

	public static void main(String args[] ) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    PrintWriter p = new PrintWriter(System.out);
	        
	    StringTokenizer st1 = new StringTokenizer(br.readLine());
	    int n = ip(st1.nextToken());
	    
		int w[] = new int[n];
		int h[] = new int[n];
		
		for(int i=0;i<n;i++){
		    StringTokenizer st2 = new StringTokenizer(br.readLine());
		    w[i] = ip(st2.nextToken());
		    h[i] = ip(st2.nextToken());
		}
	    
		int ans = Integer.MAX_VALUE;
		for(int mH = 1;mH <= 1000;mH++){
			
			int wid = 0;
			boolean done[] = new boolean[n];
			
			ArrayList<TwoInt> diff = new ArrayList<TwoInt>();
			
			int comp = 0;
			for(int i=0;i<n;i++){
				if(h[i] > mH){
					if(w[i] > mH){
						comp = n+1;
						break;
					}
					wid += h[i];
					comp++;
					done[i] = true;
				}
				else{
					if(h[i] < w[i] && w[i] <= mH)
						diff.add(new TwoInt(i,w[i] - h[i]));
					else{
						wid += w[i];
						done[i] = true;
					}
				}
			}
			
			if(comp <= n/2){
				Collections.sort(diff);
				int s = diff.size();
				int left = (n/2) - comp;
				for(int i=1;i<=Math.min(s,left);i++){
					int index = diff.get(s-i).index;
					done[index] = true;
					wid += h[index];
				}
				
				for(int i=0;i<n;i++){
					if(!done[i])
						wid += w[i];
				}
				
				//if(mH*wid < ans)
					//System.out.println(mH + " " + wid);
				
				ans = Math.min(mH*wid,ans);
			}
		}
		
		p.println(ans);
	    p.close(); 
	}
	
	public static int ip(String s){
		return Integer.parseInt(s);
	}
}

class TwoInt implements Comparable<TwoInt>{
	int index,diff;
	
	TwoInt(int i,int d){
		this.index = i;
		this.diff = d;
	}
	
	public int compareTo(TwoInt arg0) {
		return this.diff - arg0.diff;
	}
	
}
