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.BufferedWriter;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class b {

	public static PrintWriter out;
	public static int MAX;

	public static void main(String[] Args) throws Exception {
		fscan sc = new fscan(System.in);
		out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
				System.out)));
		int n = sc.nextInt();
		Person[] ps = new Person[n];
		for(int k = 0; k < n; k++){
			ps[k] = new Person(sc.nextInt(), sc.nextInt());
		}
		
		int ans = 1_000_000_000;
		for(MAX = 1; MAX <= 1000; MAX++){
			Arrays.sort(ps);
			int sum = 0;
			int max = 0;
			boolean valid = true;
			int cou = 0;
			for (int j = 0; j < n && valid; j++){
				if (ps[j].h > MAX && ps[j].w > MAX){
					valid = false;
				}
				if (ps[j].h > MAX || (ps[j].w <= MAX && ps[j].h < ps[j].w && cou + 1 <= n / 2)){
					sum+= ps[j].h;
					max = Math.max(ps[j].w, max);
					cou++;
				}
				else{
					sum+= ps[j].w;
					max = Math.max(ps[j].h, max);
				}
			}
			if(valid && cou <= n / 2){
				ans = Math.min(ans, max * sum);
			}
		}
		
		out.println(ans);
		
		out.close();
	}
	
	public static class Person implements Comparable<Person>{
		int h, w;
		Person (int w, int h){
			this.h = h; this.w = w;
		}
		
		public int compareTo(Person o){
			if(h > MAX && o.h <= MAX){
				return -1;
			}
			if(o.h > MAX && h <= MAX){
				return 1;
			}
			return (h - w) - (o.h - o.w);
		}
	}

	public static class fscan {
		StringTokenizer st;
		BufferedReader br;

		fscan(InputStream in) throws Exception {
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer(br.readLine());
		}

		String next() throws Exception {
			if (st.hasMoreTokens())
				return st.nextToken();
			st = new StringTokenizer(br.readLine());
			return next();
		}

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

		long nextLong() throws Exception {
			return Long.parseLong(next());
		}
	}
}
