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.InputMismatchException;
import java.util.ArrayList;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.List;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.Comparator;
import java.io.IOException;
import java.util.StringTokenizer;

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

class TaskB {
    class Area{
        int h;
        int w;

        public Area(int h, int w) {
            this.h = h;
            this.w = w;
        }
    }
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int [][]rect = new int[n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                rect[i][j] = in.nextInt();
            }
        }
        long max = (long) 1e12;
        for (int i = 1; i <= 1000 ; i++) {
            int cnt = n / 2;
            long width = 0;
            boolean flag = false;
            ArrayList<Area> list = new ArrayList<Area>();
            for (int j = n - 1; j >= 0 ; j--) {
                if (rect[j][1] > i){
                    if (rect[j][0] > i || cnt == 0){
                        flag = true;
                        break;
                    }
                    width += rect[j][1];
                    cnt--;
                }
                else {
                    if (rect[j][0] <= i){
                        list.add(new Area(rect[j][1],rect[j][0]));
                    }
                    else width += rect[j][0];
                }
            }
            if (flag)continue;
            Collections.sort(list, new Comparator<Area>() {
                public int compare(Area o1, Area o2) {
                    Integer a = o1.w - o1.h;
                    Integer b = o2.w - o2.h;
                    return a.compareTo(b);
                }
            });
            for (int j = list.size() - 1; j > -1; j--) {
                if (cnt > 0 && (list.get(j).w > list.get(j).h)){
                    width += list.get(j).h;
                    cnt--;
                }
                else width += list.get(j).w;
            }
            max = Math.min(max,width*i);
        }
        out.print(max+"\n");
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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


}

