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.util.Arrays;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.math.BigInteger;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Comparator;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author shu_mj @ http://shu-mj.com
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {
    Scanner in;
    PrintWriter out;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        this.in = in;
        this.out = out;
        run();
    }

    void run() {
        int n = in.nextInt();
        int[] ws = new int[n];
        int[] hs = new int[n];
        in.nextIntArray(n, ws, hs);
        int[] ss = Algo.merge(ws, hs);
        Arrays.sort(ss);
        ss = Algo.unique(ss);
        int res = Integer.MAX_VALUE;
        for (int hi = ss.length - 1; hi >= 0; hi--) {
            int h = ss[hi];
            PII[] ps = new PII[n];
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (hs[i] > h) {
                    ps[i] = new PII(hs[i], ws[i]);
                    cnt++;
                } else {
                    ps[i] = new PII(ws[i], hs[i]);
                }
            }
            if (cnt > n / 2) {
                break;
            }
            Arrays.sort(ps, new Comparator<PII>() {
                public int compare(PII o1, PII o2) {
                    int v1 = o1.y - o1.x;
                    int v2 = o2.y - o2.x;
                    return v1 - v2;
                }
            });
            int w = 0, rh = 0;
            for (PII p : ps) {
                if (p.x > p.y && p.x <= h) {
                    if (cnt < n / 2) {
                        int t = p.x; p.x = p.y; p.y = t;
                        cnt++;
                    }
                }
                w += p.x;
                rh = Math.max(rh, p.y);
            }
            res = Math.min(res, w * rh);
        }
        out.println(res);
    }
}

class Scanner {
    BufferedReader br;
    StringTokenizer st;

    public Scanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in));
        eat("");
    }

    private void eat(String s) {
        st = new StringTokenizer(s);
    }

    public String nextLine() {
        try {
            return br.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public boolean hasNext() {
        while (!st.hasMoreTokens()) {
            String s = nextLine();
            if (s == null)
                return false;
            eat(s);
        }
        return true;
    }

    public String next() {
        hasNext();
        return st.nextToken();
    }

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

    public void nextIntArray(int n, int[] as, int[] bs) {
        for (int i = 0; i < n; i++) {
            as[i] = nextInt();
            bs[i] = nextInt();
        }
    }

}

class Algo {


    public static int[] unique(int[] is) {
        return unique(is, 0, is.length);
    }

    public static int[] unique(int[] is, int b, int e) {
        if (b == e)
            return new int[0];
        int count = 1;
        for (int i = b + 1; i < e; i++) {
            if (is[i] != is[i - 1])
                count++;
        }
        int[] res = new int[count];
        res[0] = is[b];
        int id = 1;
        for (int i = b + 1; i < e; i++) {
            if (is[i] != is[i - 1])
                res[id++] = is[i];
        }
        return res;
    }

    public static int[] merge(int[] is, int[] js) {
        int in = is.length;
        int jn = js.length;
        int[] rs = new int[in + jn];
        System.arraycopy(is, 0, rs, 0, in);
        System.arraycopy(js, 0, rs, in, jn);
        return rs;
    }

}

class PII implements Comparable<PII> {
    public int x;
    public int y;

    public PII(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compareTo(PII o) {
        if (x != o.x) return x - o.x;
        return y - o.y;
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof PII)) return false;

        PII pii = (PII) o;

        if (x != pii.x) return false;
        if (y != pii.y) return false;

        return true;
    }

    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }

    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}

