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.*;

public class C529B {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		final long[] W = new long[n];
		final long[] H = new long[n];
		for (int i = 0; i < n; i++) {
			W[i] = in.nextLong();
			H[i] = in.nextLong();
		}

		Set<Long> HS = new HashSet<Long>();
		for (int i = 0; i < n; i++) {
			HS.add(H[i]);
			HS.add(W[i]);
		}

		long ans = 1000L * 1000 * 1000 * 1000;
		H: for (long h : HS) {
			PriorityQueue<Long> PQ = new PriorityQueue<Long>();

			long width = 0;

			int down = 0;
			for (int i = 0; i < n; i++) {
				if (H[i] <= h && W[i] <= h) {
					width += W[i];
					if (W[i] > H[i]) {
						PQ.offer(H[i] - W[i]);
					}
				} else if (H[i] <= h) {
					width += W[i];
				} else if (W[i] <= h) {
					width += H[i];
					down++;
				} else {
					continue H;
				}
			}
			while (!PQ.isEmpty() && down + 1 <= n / 2) {
				width += PQ.poll();
				down++;
			}
			if (down <= n / 2) {
				ans = Math.min(ans, h * width);
			}
		}
		System.out.println(ans);
	}
}