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.*;
import java.util.*;

public class Solution {
    StringTokenizer st;
    BufferedReader in;
    PrintWriter out;

    void solve() throws IOException {
        //in = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"), "ISO-8859-1"));
        //out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt"), "ISO-8859-1"));

        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        Locale.setDefault(Locale.ENGLISH);

        int n = nextInt();
        int[][] a = new int[n][2];

        for (int i = 0; i < n; i++) {
            a[i] = new int[]{nextInt(), nextInt()};
        }

        Arrays.sort(a, new comp());

        final int INF = (int) 1e9;
        int ans = INF;

        loop: for (int i = 1; i <= 1000; i++) {
            int cnt = 0;
            int len = 0;

            boolean[] used = new boolean[n];
            for (int j = 0; j < n; j++) {
                if (a[j][1] > i) {
                    if (a[j][0] > i || cnt + 1 > n  / 2) {
                        continue loop;
                    }

                    len += a[j][1];
                    used[j] = true;
                    cnt++;
                }
            }

            for (int j = 0; j < n; j++) {
                if (used[j]) {
                    continue;
                }

                if (a[j][0] <= i && cnt + 1 <= n / 2 && a[j][1] - a[j][0] < 0) {
                    len += a[j][1];
                    cnt++;
                } else {
                    len += a[j][0];
                }
            }

            ans = Math.min(ans, len * i);
        }

        out.print(ans);

        in.close();
        out.close();
    }

    class comp implements Comparator<int[]> {

        @Override
        public int compare(int[] o1, int[] o2) {
            return Integer.compare(o1[1] - o1[0], o2[1] - o2[0]);
        }
    }

    public static void main(String[] args) throws IOException {
        new Solution().solve();
    }

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

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

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

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