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.*;
import java.math.BigInteger;
import java.util.*;


public class B {

    class Man implements Comparable<Man>{
        int w,h;

        public Man(int w, int h) {
            this.w = w;
            this.h = h;
        }

        @Override
        public int compareTo(Man o) {
            return (h-w)-(o.h-o.w);
        }
    }

    void solve() throws IOException {
        int n=nextInt();
        Man[] a=new Man[n];
        int result=1000000000;
        for(int i=0;i<n;i++){
            a[i]=new Man(nextInt(),nextInt());
        }
        Arrays.sort(a);
        for(int i=1;i<=1000;i++){
            int count=0;
            boolean[] used=new boolean[n];
            boolean good=true;
            for(int j=0;j<n;j++){
                if(a[j].h>i&&a[j].w>i){
                    good=false;
                    break;
                }
                if(a[j].h>i){
                    used[j]=true;
                    count++;
                }
            }
            if(count>n/2||!good)continue;
            for(int j=0;j<n&&count<n/2;j++) {
                if(a[j].h>=a[j].w)break;
                if (!used[j]&&a[j].w<=i){
                    used[j]=true;
                    count++;
                }
            }
            int cur=0;
            for(int j=0;j<n;j++)
                if(used[j])cur+=a[j].h;
            else
                    cur+=a[j].w;
            cur*=i;
            if(cur<result)
                result=cur;
        }
        out.println(result);
    }

    public static void main(String[] args) throws IOException {
        new B().run();
    }

    void run() throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
//      reader = new BufferedReader(new FileReader("input.txt"));
        tokenizer = null;
        out = new PrintWriter(new OutputStreamWriter(System.out));
//      out = new PrintWriter(new FileWriter("output.txt"));
        solve();
        reader.close();
        out.flush();

    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}
