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.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class VK_R1_B {
    static int n;
    static pnt inp[];
    static int minW[];

    public static int getMinW(int h) {
        int width = 0;
        int count = 0;
        for (int i = 0; i < inp.length; i++) {
            if (inp[i].x > h && inp[i].y > h)
                return Integer.MAX_VALUE;
        }
        for (int i = 0; i < inp.length; i++) {
            if (inp[i].y > h && inp[i].x <= h) {
                if (count >= n / 2)
                    return Integer.MAX_VALUE;
                width += inp[i].y;
                count++;
            } else if (inp[i].x > h && inp[i].y <= h) {
                width += inp[i].x;
            }
        }
        for (int i = 0; i < inp.length; i++) {
            if (inp[i].y <= h && inp[i].x <= h) {
                if (inp[i].x <= inp[i].y || count >= n / 2)
                    width += inp[i].x;
                else {
                    count++;
                    width += inp[i].y;
                }
            }
        }
        return width;
    }

    static class pnt implements Comparable<pnt> {
        int x;
        int y;

        public pnt(int xx, int yy) {
            x = xx;
            y = yy;
        }

        @Override
        public int compareTo(pnt o) {
            return (o.x - o.y) - (x - y);
        }

    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        n = in.readInt();
        inp = new pnt[n];
        int MAX = 1002;
        for (int i = 0; i < n; i++) {
            inp[i] = new pnt(in.readInt(), in.readInt());
        }
        Arrays.sort(inp);
//      for (int i = 0; i < inp.length; i++) {
//          System.out.println(inp[i].x + " " + inp[i].y);
//      }
        minW = new int[MAX + 2];
        for (int i = 0; i < minW.length; i++) {
            minW[i] = getMinW(i);
        }
        int lo = 0;
        int hi = MAX * MAX * n;
        int ans = Integer.MAX_VALUE;
        while (lo < hi) {
            int currentArea = lo + (hi - lo) / 2;
            boolean flag = false;
            for (int i = 1; i * i <= currentArea; i++) {
                int h1 = currentArea / i;
                int h2 = i;
                if (minW[Math.min(MAX, h1)] <= h2
                        || minW[Math.min(MAX, h2)] <= h1) {
                    hi = currentArea;
                    ans = currentArea;
                    flag = true;
                    break;
                }
            }
            if (!flag)
                lo = currentArea + 1;
        }
        System.out.println(ans);
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1000];
        private int curChar, numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private String readLine0() {
            StringBuffer buf = new StringBuffer();
            int c = read();
            while (c != '\n' && c != -1) {
                buf.appendCodePoint(c);
                c = read();
            }
            return buf.toString();
        }

        public String readLine() {
            String s = readLine0();
            while (s.trim().length() == 0)
                s = readLine0();
            return s;
        }

        public String readLine(boolean ignoreEmptyLines) {
            if (ignoreEmptyLines)
                return readLine();
            else
                return readLine0();
        }

        public char readCharacter() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return (char) c;
        }

        public double readDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, readInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
    }
}
