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.*;
import java.io.*;

public class B
{
   public static void main(String[] args)
   {
      PrintWriter out = new PrintWriter(System.out);
      new B(new FastScanner(), out);
      out.close();
   }

   public B(FastScanner in, PrintWriter out)
   {
      int N = in.nextInt();
      Person[] vs = new Person[N];
      for (int i=0; i<N; i++)
         vs[i] = new Person(in.nextInt(), in.nextInt());
      Arrays.sort(vs);
     
      long res = Long.MAX_VALUE;
      boolean[] onFloor = new boolean[N];
      for (int h=1; h<=1000; h++)
      {
         boolean passed = true;
         Arrays.fill(onFloor, false);
         int numFloor = 0;
         for (int i=0; i<N; i++)
         {
            if (vs[i].h > h)
            {
               if (vs[i].w > h)
               {
                  passed = false;
               }
               onFloor[i] = true;
               numFloor++;
            }
         }

         if (!passed || numFloor > N / 2)
            continue;
      
         for (int i=0; i<N; i++)
         {
            if (numFloor == N / 2) break;
            if (vs[i].w > vs[i].h && vs[i].w <= h)
            {
               onFloor[i] = true;
               numFloor++;
            }
         }

         int runningWidth = 0;
         for (int i=0; i<N; i++)
         {
            if (onFloor[i])
            {
               runningWidth += vs[i].h;
            }
            else
            {
               runningWidth += vs[i].w;
            }
         }

         res = Math.min(res, runningWidth*1L*h);
      }

      out.println(res);
   }
}

class Person implements Comparable<Person>
{
   int w, h, diff;

   Person(int ww, int hh)
   {
      w=ww; h=hh;

      diff = h-w;
   }

   public int compareTo(Person rhs)
   {
      return diff-rhs.diff;
   }
}

class FastScanner{
   private InputStream stream;
   private byte[] buf = new byte[1024];
   private int curChar;
   private int numChars;

   public FastScanner()
   {
      stream = System.in;
   }

   int read()
   {
      if (numChars == -1)
         throw new InputMismatchException();
      if (curChar >= numChars){
         curChar = 0;
         try{
            numChars = stream.read(buf);
         } catch (IOException e) {
            throw new InputMismatchException();
         }
         if (numChars <= 0)
            return -1;
      }
      return buf[curChar++];
   }

   boolean isSpaceChar(int c)
   {
      return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
   }
   
   boolean isEndline(int c)
   {
      return c=='\n'||c=='\r'||c==-1;
   }

   int nextInt()
   {
      return Integer.parseInt(next());
   }
   
   long nextLong()
   {
      return Long.parseLong(next());
   }

   double nextDouble()
   {
      return Double.parseDouble(next());
   }

   String next(){
      int c = read();
      while (isSpaceChar(c))
         c = read();
      StringBuilder res = new StringBuilder();
      do{
         res.appendCodePoint(c);
         c = read();
      }while(!isSpaceChar(c));
      return res.toString();
   }
   
   String nextLine(){
      int c = read();
      while (isEndline(c))
         c = read();
      StringBuilder res = new StringBuilder();
      do{
         res.appendCodePoint(c);
         c = read();
      }while(!isEndline(c));
      return res.toString();
   }
}
