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.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;



   
public class Main {
    public static void main(String[] args) throws IOException{
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
           
        //InputStream inputStream = new FileInputStream("input.txt");
        //OutputStream outputStream = new FileOutputStream("output.txt");
           
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
           
        TaskB solver = new TaskB();
        solver.solve(in, out);
        
        out.close();
    }
}
   
class TaskB {
    
	
	
	public void solve(InputReader in, OutputWriter out) {
		
		int n = in.nextInt();
		Pair[] a = new Pair[n];
		for(int i=0; i<n; i++){
			int w = in.nextInt();
			int h = in.nextInt();
			a[i] = new Pair(w,h);
		}
		Arrays.sort(a);
		
		boolean[] used;;
		long cnt,h,w;
		
		long min = Long.MAX_VALUE;
		for(int maxH=1; maxH<=1000; maxH++){
			cnt=0; used = new boolean[n]; w = 0;
			h = 0;
			for(int i=0; i<n; i++){
				if(a[i].h>maxH){
					cnt++; w+=(long)a[i].h; used[i] = true; 
					h = Math.max(h,a[i].w);
				}
			}
			if(cnt>n/2 || h>maxH) continue;
			for(int i=0; i<n; i++){
				if((cnt+1)<=n/2 && !used[i] && a[i].w<=maxH && a[i].h<a[i].w){
					cnt++; used[i]=true; w+=(long)a[i].h;
					h = Math.max(h, a[i].w);
				}else if(!used[i]){
					w+=(long)a[i].w;
					h = Math.max(h, a[i].h);
				}
			}
			
			min = Math.min(min, w*h);
			
		}
		
		
		out.writeln(min);
    }	
}

class Pair implements Comparable<Pair>{
	
	public Pair(int w, int h){
		this.w = w;
		this.h = h;
	}
	
	public int compareTo(Pair p){
		return (h-w)-(p.h-p.w);
	}
	
	int w,h;
}


class InputReader{
       
    BufferedReader reader;
    StringTokenizer tokenizer;
       
    public InputReader(InputStream stream){
        tokenizer = null;
        reader = new BufferedReader(new InputStreamReader(stream));
    }
       
    public String next(){
        while(tokenizer==null || !tokenizer.hasMoreTokens()){
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
           
        return tokenizer.nextToken();
    }
       
    public String nextLine(){
        tokenizer = null;
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException();
        }
    }
       
    public int nextInt(){
        return Integer.parseInt(next());
    }
       
    public long nextLong(){
        return Long.parseLong(next());
    }
       
    public double nextDouble(){
        return Double.parseDouble(next());
    }
       
    public int[] nextIntArray(int n){
        int[] res = new int[n];
        for(int i=0; i<n; i++)
            res[i] = nextInt();
           
        return res;
    }
       
}
   
class OutputWriter{
       
    PrintWriter out;
       
    public OutputWriter(OutputStream stream){
        out = new PrintWriter(new BufferedWriter(
                new OutputStreamWriter(stream)));
    }
       
    public void write(Object ...o){
        for(Object cur : o)
            out.print(cur);
    }
       
    public void writeln(Object ...o){
        write(o);
        out.println();
    }
       
    public void flush(){
        out.flush();
    }
       
    public void close(){
        out.close();
    }
       
}