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 vkB {
	static InputReader in = new InputReader();
	static String str;
	static String[] arr;

	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(in.readLine());
		int[] wi = new int[n];
		int[] hi = new int[n];
		for(int i = 0; i < n; i++) {
			str = in.readLine();
			wi[i] = Integer.parseInt(str.substring(0, str.indexOf(" ")));
			hi[i] = Integer.parseInt(str.substring(str.indexOf(" ") + 1));
		}
		long minarea = Long.MAX_VALUE >> 1;
		for(int i = 0; i <= 1000; i++) {//height
			int maxswitch = n / 2;
			int width = 0;
			boolean works = true;
			for(int j = 0; j < n; j++) {
				if(hi[j] > i) {
					if(wi[j] > i) {
						works = false;
					} else {
						width += hi[j];
						maxswitch--;
						if(maxswitch < 0) {
							works = false;
						}
					}
				} else {
					width += wi[j];
				}
			}
			PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
			for(int j = 0; j < n && works; j++) {
				if(wi[j] <= i) {
					pq.add(hi[j] - wi[j]);
				}
			}
			for(int j = 0; j < maxswitch && !pq.isEmpty(); j++) {
				int temp = pq.remove();
				if(temp < 0) {
					width += temp;
				}
			}
			if(works) {
				minarea = Math.min(minarea, (long) width * i);
			}
		}
		System.out.println(minarea);
	}

	static class InputReader {
		BufferedReader br;

		public InputReader() {
			try {
				br = new BufferedReader(new FileReader("vkB.in"));
			} catch (Exception e) {
				br = new BufferedReader(new InputStreamReader(System.in));
			}
		}

		public String readLine() throws Exception {
			return br.readLine();
		}
	}
}