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.awt.Container;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.concurrent.LinkedBlockingDeque;

import javax.swing.border.Border;

public class a {

	public static long mod = (long) Math.pow(10, 9) + 7;

	private static class node implements Comparable<node> {
		int x;
		int y;

		node(int an, int t) {
			x = an;
			y = t;
		}

		@Override
		public int compareTo(node o) {

			if (o.x - o.y < x - y)
				return 1;
			else if (o.x - o.y > x - y)
				return -1;
			return 0;

		}

	}

	public static class point {
		int screen;
		int order;

		point(int x, int y) {
			screen = x;
			order = y;

		}

	}

	public static int ch(long y) {
		int r = Long.bitCount(y);
		return r;
	}

	public static long gcd(long x, long y) {
		if (y == 0)
			return x;

		return gcd(y, x % y);
	}

	public static boolean ch[] = new boolean[10000005];
	public static ArrayList<Integer> prime = new ArrayList();

	// public static Queue<Integer> pp;

	public static void sieve(int k) {
		ch[0] = ch[1] = true;

		for (int i = 2; i <= k; i++) {
			if (!ch[i]) {
				prime.add(i);
				// pp.add(i);
				for (long j = (long) i * (long) i; j <= k; j += i) {
					ch[(int) j] = true;
				}
			}
		}

	}

	public static long pw(int x, int power, int mod) {
		if (power == 1)
			return x % mod;
		else if (power % 2 == 0)
			return pw((x % mod * x % mod) % mod, power / 2, mod);
		else
			return (pw(x, power - 1, mod) % mod * x % mod) % mod;

	}

	public static String addToString(String a, int index, char b) {
		String ans = "";
		for (int i = 0; i < a.length(); i++) {
			if (i == index) {
				ans += b;
				index = -1;
				i--;
				continue;
			}
			ans += a.charAt(i);
		}
		return ans;
	}

	public static int bit[];

	public static void add(int idx, int cost) {
		while (idx < bit.length) {
			bit[idx] += cost;
			idx += (idx & -idx);
		}

	}

	public static int get(int idx) {
		int res = 0;
		while (idx > 0) {
			res += bit[idx];
			idx -= (idx & -idx);
		}
		return res;
	}

	public static int dx[] = { 0, 1, 0, -1 };
	public static int dy[] = { 1, 0, -1, 0 };

	public static boolean ok[];
	public static node a[];

	public static int getSum(int len, int max) {
		int sum = 0;
		for (int i = 0; i < a.length; i++) {
			if (!ok[i]) {
				if (a[i].x > max && a[i].y > max)
					return -1;
				else if (a[i].x > max) {
					if (len == 0)
						return -1;
					len--;
					sum += a[i].x;
					ok[i] = true;
				}

			}
		}
		for (int i = 0; i < a.length; i++) {
			if (!ok[i]) {
				if (len > 0 && a[i].x < a[i].y && a[i].y <= max) {
					sum += a[i].x;
					len--;
				} else
					sum += a[i].y;

			}
		}
		return sum;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader in = new BufferedReader(new FileReader(
		// "corporate_gifting.txt"));
		StringBuilder qq = new StringBuilder();
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		// PrintWriter out = new PrintWriter(new FileWriter("out.txt"));
		// System.out.println('a' - 'A');

		String y[] = in.readLine().split(" ");
		int n = Integer.parseInt(y[0]);

		a = new node[n];
		for (int i = 0; i < n; i++) {
			y = in.readLine().split(" ");
			a[i] = new node(Integer.parseInt(y[1]), Integer.parseInt(y[0]));
		}
		Arrays.sort(a);

		int ans = Integer.MAX_VALUE;
		for (int i = 1; i <= 1000; i++) {
			ok = new boolean[n];
			int w = getSum(n / 2, i);
			if (w == -1)
				continue;
			ans = Math.min(ans, i * w);
		}

		System.out.println(ans);

		out.close();

	}
}