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.Reader;
import java.util.Arrays;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Comparator;
import java.io.IOException;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Denis Nedelyaev
 */
public class Main {
	public static void main(String[] args) throws Exception {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB(in, out);
		solver.solve(1);
		out.close();
	}
}

class TaskB {
    private final FastScanner in;
    private final PrintWriter out;
    private int n;
    private Comparator<Person> comparator;
    private Person[] people;

    public TaskB(FastScanner in, PrintWriter out) {
        this.in = in;
        this.out = out;
    }

    public void solve(int testNumber) throws IOException {
        n = in.nextInt();
        people = new Person[n];
        for (int i = 0; i < n; i++) {
            people[i] = new Person(in.nextInt(), in.nextInt());
        }
        comparator = (a, b) -> Integer.compare(a.h - a.w, b.h - b.w);
        Arrays.sort(people, comparator);

        long minArea = Long.MAX_VALUE;
        for (int maxHeight = 1; maxHeight <= 1000; maxHeight++) {
            minArea = Math.min(minArea, minArea(maxHeight));
        }
        out.println(minArea);
    }

    public long minArea(int maxHeight) {
        int count = 0;
        for (Person p : people) {
            if (p.h > maxHeight) {
                if (p.w > maxHeight) {
                    return Long.MAX_VALUE;
                }
                count++;
                if (count > n / 2) {
                    return Long.MAX_VALUE;
                }
            }
        }
        long w = 0;
        for (Person p : people) {
            if (p.h > maxHeight) {
                w += p.h;
            } else if (p.w <= maxHeight && p.h < p.w && count + 1 <= n / 2) {
                w += p.h;
                count++;
            } else {
                w += p.w;
            }
        }
        return maxHeight * w;
    }

    private static class Person {
        final int w, h;

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

class FastScanner {
    private BufferedReader br;
    private String line = "";
    private int pos;

    public FastScanner(InputStream is) {
        this(new BufferedReader(new InputStreamReader(is)));
    }

    public FastScanner(Reader reader) {
        br = new BufferedReader(reader);
    }

    public int nextInt() throws IOException {
        if (!goToNextToken()) {
            return 0;
        }
        return readInt();
    }

    private boolean goToNextToken() throws IOException {
        if (br == null) {
            return false;
        }

        while (pos == line.length()) {
            line = br.readLine();

            if (line == null) {
                br = null;
                return true;
            }

            pos = 0;

            skipWhitespace();
        }

        return true;
    }

    private int readInt() {
        int result = 0;

        int sign = 1;
        if (line.charAt(pos) == '-') {
            sign = -1;

            pos++;
        }

        while (pos < line.length()) {
            char c = line.charAt(pos);

            if (c == ' ' || c == '\t') {
                break;
            }

            pos++;

            result *= 10;
            result += c - '0';
        }

        skipWhitespace();

        return sign * result;
    }

    private void skipWhitespace() {
        while (pos < line.length()) {
            char c = line.charAt(pos);

            if (c != ' ' && c != '\t') {
                break;
            }

            pos++;
        }
    }
}

