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.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;

public class Main
{

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Person> friends = new ArrayList<Person>();
		int maxHeight = -1;
		
		for(int i = 0; i < n; i++)
		{
			int width = sc.nextInt();
			int height = sc.nextInt();
			friends.add(new Person(width, height));
			
			//We compute the maximum height along the way, which we are given is at most 1000.
			if(height > maxHeight)
				maxHeight = height;
			
			if(width > maxHeight)
				maxHeight = width; //This person might lie down, so we need to check their width as well.
		}
		sc.close();
		
		//We sort out list of people by how much they can decrease the width by lying down.
		//Then we loop over all of the possible heights. We choose people to lie down who can
		//improve the width without exceeding the maximum height or the limit of n/2 people
		//lying down.
		
		Collections.sort(friends);
		int bestArea = -1;
		for(int currHeight = 1; currHeight <= maxHeight; currHeight++)
		{
			int totalWidth = 0;
			boolean valid = true;
			int flipCount = 0;
			boolean[] flipped = new boolean[n];
			
			//We first check that it is possible to flip people so that
			//the given height is achievable.
			for(int i = 0; i < n; i++)
			{
				Person next = friends.get(i);
				if(next.height > currHeight)
				{
					if(next.width > currHeight)
					{
						//This person does not fit either horizontally or vertically.
						valid = false;
					}
					else
					{
						//We have to make this person lie down.
						flipped[i] = true;
						flipCount++;
						if(flipCount > n/2)
							valid = false; //We can't make this many people lie down.
					}
				}
				else
					flipped[i] = false; //This person does not have to lie down, but may be able to later.
			}
			
			if(valid)
			{
				for(int i = 0; i < n; i++)
				{
					Person next = friends.get(i);
					if(flipped[i])
					{
						//We already know that this person has to lie down.
						totalWidth += next.height;
						//System.out.println("Lying down: " + Integer.toString(next.width) + ", " + Integer.toString(next.height));
					}
					else if(flipCount < n/2 && next.width > next.height && next.width <= currHeight)
					{
						//We can have this person also lie down, since it will decrease the width.
						//Since we have sorted in order of increasing (height - width), we know that
						//this is actually the best solution.
						totalWidth += next.height;
						flipCount++;
						//System.out.println("Lying down: " + Integer.toString(next.width) + ", " + Integer.toString(next.height));
					}
					else
					{
						//This person will stand up.
						totalWidth += next.width;
						//System.out.println("Standing up: " + Integer.toString(next.width) + ", " + Integer.toString(next.height));
					}
				}
				
				int currArea = totalWidth*currHeight;
				//System.out.println(currArea);
				if(bestArea < 0 || currArea < bestArea)
					bestArea = currArea; //Use this arrangement if it is the best seen so far.
			}
		}
		System.out.println(bestArea);
	}

	static class Person implements Comparable<Person>
	{
		int width;
		int height;
		
		public Person(int w, int h)
		{
			width = w;
			height = h;
		}
		
		public int compareTo(Person other)
		{
			return ((Integer) (height - width)).compareTo((Integer) (other.height - other.width));
		}
	}
}
