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 PrBPhoto {
	public static void main(String[] args) throws IOException {
		new PrBPhoto().run();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st;

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

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

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out, true);
		solve();
		out.flush();
	}

	class Person {
		int w;
		int h;

		public Person() {
		}

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

		@Override
		public String toString() {
			return this.w + " " + this.h;
		}
	}

	void solve() throws IOException {
		int n = nextInt();
		Person[] all = new Person[n];
		for (int i = 0; i < n; i++) {
			all[i] = new Person(nextInt(), nextInt());
		}
		Arrays.sort(all, new Comparator<Person>() {

			@Override
			public int compare(Person o1, Person o2) {
				return -Integer.compare(o1.h, o2.h);
			}
		});
		if (n == 1) {
			out.println(all[0].w * all[0].h);
			return;
		}
		long ans = Long.MAX_VALUE;
		for (int maxH = 1000; maxH >= 1; maxH--) {
			for (int i = 0; i < n; i++) {
				if (all[i].h > maxH && all[i].w > maxH) {
					out.println(ans);
					return;
				}
			}
			long temp = 0;
			int i = 0;
			for (; i < n && all[i].h > maxH; i++) {
				temp += all[i].h;
			}
			int ost = (n) / 2 - i;
			if (ost < 0) {
				continue;
			}
			ArrayList<Integer> ts = new ArrayList<Integer>();
			for (; i < n; i++) {
				if (all[i].w > maxH) {
					temp += all[i].w;
				} else {
					temp += all[i].h;
					ts.add(all[i].w - all[i].h);
				}
			}
			Collections.sort(ts);
			while (ts.size() > ost || (!ts.isEmpty() && ts.get(0) <= 0)) {
				temp += ts.remove(0);
			}
			ans = Math.min(ans, temp * maxH);
		}
		out.println(ans);
	}
}
