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 Solve {

    class Man implements Comparable<Man> {
        int h, w;

        Man(int w, int h) {
            this.w = w;
            this.h = h;
        }

        @Override
        public int compareTo(Man o) {
            return Integer.compare(h - w, o.h - o.w);
        }
    }

    void solve() throws IOException {
        int n = in.nextInt();
        Man[] m = new Man[n];
        int minH = 0;
        for (int i = 0; i < n; ++i) {
            m[i] = new Man(in.nextInt(), in.nextInt());
            minH = Math.max(minH, Math.min(m[i].h, m[i].w));
        }
        Arrays.sort(m, new Comparator<Man>() {
            @Override
            public int compare(Man o1, Man o2) {
                return Integer.compare(o1.h, o2.h);
            }
        });
        int ans = Integer.MAX_VALUE;
        for (int i = 0, H = minH; H < 1003; H++) {
            while (i < n && m[i].h <= H) {
                i++;
            }
            Man[] hz = Arrays.copyOf(m, i);
            int can = n / 2;
            int res = 0;
            for (int j = i; j < n; j++) {
                res += m[j].h;
                can--;
            }
            if (can < 0) continue;
            Arrays.sort(hz);
            for (Man man : hz) {
                if (can > 0 && man.w > man.h && man.w <= H) {
                    res += man.h;
                    can--;
                } else {
                    res += man.w;
                }
            }
            ans = Math.min(ans, res * H);
        }
        out.println(ans);
    }

    static FastReader in;
    static PrintWriter out;
    static PrintStream err;

    public static void main(String[] args) {
        try {
            in = new FastReader();
            out = new PrintWriter(System.out);
            err = System.err;
            new Solve().solve();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    FastReader(InputStream is) {
        br = new BufferedReader(new InputStreamReader(is));
    }

    FastReader() {
        this(System.in);
    }

    FastReader(String file) throws FileNotFoundException {
        this(new FileInputStream(file));
    }

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

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