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
/**  _ _
 * \(^.^\)
 *  ( 8 ;)
 *  ( __;)
 *   V  V
 * by Abril
 */

import java.io.*;
import java.util.*;

public class Main {
	
	class E implements Comparable<E> {
		int v;
		int id;
		
		E(int v, int id) {
			this.v = v;
			this.id = id;
		}

		@Override
		public int compareTo(E o) {
			return Integer.compare(v, o.v);
		}
	}
	
	void solve() {
		int n = in.nextInt();
		int[][] a = new int[n][2];
		for (int i = 0; i < n; i++) {
			a[i][0] = in.nextInt(); // w -> h
			a[i][1] = in.nextInt(); // h -> w
		}
		boolean[] caido = new boolean[n];
		int respuesta = (int)1e9;
		for (int t = 0; t < 2; t++) {
			for (int i = 0; i < n; i++) {
				int caidos = 0;
				Arrays.fill(caido, false);
				if (t == 0) {
					caidos++;
					caido[i] = true;
				}
				for (int j = 0; j < n; j++) {
					if (j == i) {
						continue;
					}
					if (a[j][1] > a[i][t]) {
						caidos++;
						caido[j] = true;
					}
				}
				if (caidos > n / 2) {
					continue;
				}
				ArrayList<E> lista = new ArrayList<>();
				for (int j = 0; j < n; ++j) {
					if (j == i || caido[j]) {
						continue;
					}
					if (a[j][0] <= a[i][t] && a[j][1] < a[j][0]) {
						lista.add(new E(a[j][1] - a[j][0], j));
					}
				}
				Collections.sort(lista);
				for (int j = 0; j < lista.size(); ++j) {
					if (caidos < n / 2) {
						++caidos;
						caido[lista.get(j).id] = true;
					}
				}
				int W = 0, H = 0;
				for (int j = 0; j < n; ++j) {
					int w = a[j][0];
					int h = a[j][1];
					if (caido[j]) {
						int tmp = w;
						w = h;
						h = tmp;
					}
					W += w;
					H = Math.max(H, h);
				}
				respuesta = Math.min(respuesta, W * H);
			}
		}
		out.println(respuesta);
	}
	
	void run() {
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}
	
	InputReader in;
	PrintWriter out;
	
	class InputReader {
		BufferedReader br;
		StringTokenizer st;
		
		InputReader(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
			st = null;
		}
		
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}