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.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
public class _529B {

}

 */

public class _529B {

	class pair
	{
		int w;
		int h;
		int mh;
		int whd;
		public pair(int w, int h, int mh) {
			super();
			this.w = w;
			this.h = h;
			this.mh = mh;
			this.whd = w - h;
			if(this.whd > 0 && this.w > this.mh)
			{
				this.whd = -5000;
			}
		}


	}

	public void solve() throws FileNotFoundException {
		InputStream inputStream = System.in;

		InputHelper inputHelper = new InputHelper(inputStream);

		PrintStream out = System.out;

		//actual solution
		int n = inputHelper.readInteger();

		pair[] pa = new pair[n];

		for(int i = 0; i < n; i++)
		{
			int w = inputHelper.readInteger();
			int h = inputHelper.readInteger();

			pair pair = new pair(w, h, -1);

			pa[i] = pair;
		}

		int ans = 1000000000;
		for(int ch = 1000; ch >= 1; ch--)
		{
			PriorityQueue<pair> pq = new PriorityQueue<_529B.pair>(n, new Comparator<pair>() {

				public int compare(pair o1, pair o2) {
					if(o1.h <= o1.mh && o2.h <= o2.mh)
					{
						return o2.whd - o1.whd;
					}
					else if(o1.h > o1.mh && o2.h < o2.mh)
					{
						return -1;
					}
					else if(o1.h <= o1.mh && o2.h > o2.mh)
					{
						return 1;
					}
					return 0;
				}
			});

			for(int i = 0; i < n; i++)
			{
				pq.add(new pair(pa[i].w, pa[i].h, ch));
			}

			int wr = 0;
			boolean p = true;

			for(int i = 0; i < n / 2; i++)
			{
				pair pair = pq.poll();

				if(pair.h > pair.mh)
				{
					if(pair.w <= ch)
					{
						wr += pair.h;
					}
					else
					{
						p = false;
						break;
					}
				}
				else if(pair.whd > 0)
				{
					wr += pair.h;
				}
				else
				{
					wr += pair.w;
				}
			}

			if(p)
			for(int i = n / 2; i < n; i++)
			{
				pair pair = pq.poll();
				if(pair.h > pair.mh)
				{
					p = false;
					break;
				}
				wr += pair.w;
			}

			if(p)
				ans = Math.min(ans, wr * ch);
		}

		System.out.println(ans);
		//end here
	}

	public static void main(String[] args) throws FileNotFoundException {
		(new _529B()).solve();
	}

	class InputHelper {
		StringTokenizer tokenizer = null;
		private BufferedReader bufferedReader;

		public InputHelper(InputStream inputStream) {
			InputStreamReader inputStreamReader = new InputStreamReader(
					inputStream);
			bufferedReader = new BufferedReader(inputStreamReader, 16384);
		}

		public String read() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					String line = bufferedReader.readLine();
					if (line == null) {
						return null;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					e.printStackTrace();
				}
			}

			return tokenizer.nextToken();
		}

		public Integer readInteger() {
			return Integer.parseInt(read());
		}

		public Long readLong() {
			return Long.parseLong(read());
		}
	}
}