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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class B {
	static InputStreamReader isr = new InputStreamReader(System.in);
	static BufferedReader br = new BufferedReader(isr);

	static int[] readIntArray() throws IOException {
		String[] v = br.readLine().split(" ");
		int[] ans = new int[v.length];

		for (int i = 0; i < ans.length; i++) {
			ans[i] = Integer.valueOf(v[i]);
		}

		return ans;
	}

	static class Person implements Comparable<Person> {
		public int w;
		public int h;

		public Person(int[] wh) {
			this.w = wh[0];
			this.h = wh[1];
		}

		@Override
		public int compareTo(Person arg0) {
			return -new Integer(w - h).compareTo(arg0.w - arg0.h);
		}
	}

	static int[][] wh;
	static int n;

	public static void main(String[] args) throws IOException {
		n = readIntArray()[0];
		wh = new int[n][];
		for (int i = 0; i < wh.length; i++) {
			wh[i] = readIntArray();
		}
		
		long ans = Long.MAX_VALUE;
		for (int i = 0; i < wh.length; i++) {			
			long a1 = getSize(wh[i][0], wh[i][1], i);
			long a2 = getSize(wh[i][1], wh[i][0], i);
			ans = Math.min(ans, Math.min(a1, a2));
		}

		System.out.println(ans);
	}

	static long getSize(int cw, int ch, int ind) {
		int laidCnt = wh[ind][0] == cw ? 0 : 1;
		int max = n / 2;
		List<Person> free = new ArrayList<Person>();
		for (int j = 0; j < wh.length; j++) {
			if (j == ind)
				continue;

			if (wh[j][1] > ch) {
				if (wh[j][0] > ch) {
					laidCnt = 100000;
					break;
				} else {
					cw += wh[j][1];
					laidCnt++;
				}
			} else {
				if (wh[j][0] > ch) {
					cw += wh[j][0];
				} else {
					free.add(new Person(wh[j]));
				}
			}
		}

		if (laidCnt <= max) {
			Collections.sort(free);
						
			for (int j = 0; j < free.size(); j++) {
				if (laidCnt < max) {
					if (free.get(j).w <= free.get(j).h) {
						cw += free.get(j).w;
					} else {
						cw += free.get(j).h;
						laidCnt++;
					}
				} else {
					cw += free.get(j).w;	
				}				
			}			

			return cw * ch;
		} else {
			return Long.MAX_VALUE;
		}

	}

}
