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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;


public class B {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;
    
	public void solve() throws IOException {				
		int N = nextInt();
        int[][] A = new int[N][];
		for (int i = 0; i < N; i++) {
            A[i] = new int[] {nextInt(), nextInt()};
        }

        Arrays.sort(A, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                int diff1 = a[0] - a[1];
                int diff2 = b[0] - b[1];
                return diff1 > diff2? -1: 1;
            }
        });

        long INF = Integer.MAX_VALUE / 2;
        long best = Long.MAX_VALUE / 2;
        next: for (int h = 0; h <= 1000; h++) {
            long ans = 0;

            ArrayList<Integer> possible = new ArrayList<Integer>();
            int used = 0;
            for (int i = 0; i < N; i++) {
                if (A[i][1] > h && A[i][0] > h) continue next;

                if (A[i][0] > h) {
                    ans += A[i][0];
                } else if (A[i][1] > h) {
                    ans += A[i][1];
                    used++;
                } else {
                    if (A[i][0] <= A[i][1]) {
                        ans += A[i][0];
                    } else {
                        possible.add(i);
                    }
                }
            }

            int remain = N / 2 - used;
            if (remain < 0) continue next;

            for (int i: possible) {
                if (remain > 0) {
                    ans += A[i][1];
                    remain--;
                } else {
                    ans += A[i][0];
                }
            }
            best = Math.min(best, ans * h);
        }
        out.println(best);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new B().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}
