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.*;

public class B {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    final long[] W = new long[n];
    final long[] H = new long[n];
    for(int i=0; i<n; i++) {
      W[i] = in.nextLong();
      H[i] = in.nextLong();
    }

    Set<Long> HS = new HashSet<Long>();
    for(int i=0; i<n; i++) {
      HS.add(H[i]);
      HS.add(W[i]);
    }

    long ans = 1000L*1000*1000*1000;
  H:for(long h : HS) {
      PriorityQueue<Long> PQ = new PriorityQueue<Long>();

      long width = 0;

      int down = 0;
      for(int i=0; i<n; i++) {
        if(H[i]<=h && W[i]<=h) {
          width += W[i];
          if(W[i] > H[i]) {
            PQ.offer(H[i] - W[i]);
          }
        } else if(H[i] <= h) {
          width += W[i];
        } else if(W[i] <= h) {
          width += H[i];
          down++;
        } else {
          continue H;
        }
      }
      while(!PQ.isEmpty() && down+1<=n/2) {
        width += PQ.poll();
        down++;
      }
      if(down <= n/2) {
        ans = Math.min(ans, h*width);
      }
    }
    System.out.println(ans);
  }
}
