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
#encoding:utf-8
import heapq
__author__ = 'bowiehsu'
n = input()
X = 1000000005
W,H = [],[]
for _ in range(n):
    ini = [int(i) for i in ((raw_input()).split(' '))]
    W.append(ini[0])
    H.append(ini[1])
#print W,H
def proces (h):
    w = 0
    k = 0
    heap = []
    #因为题目中高度的范围为1到1000，所以迭代查找宽度、高度与1到1000这些数之间的关系
    for i in range(n):
        #if a high person fits into heright h,we leave him as is.
        # if a wide person fits into h.we leave him staying.
        if H[i] <= h and W[i] > h:
            w += W[i]
        # If a wide person fits into height H in both ways,
        elif H[i] <= h and W[i] <= h:
            w += W[i]
            heap.append(W[i]-H[i])
        #If a high person doesn't fit into height H, the we
        # have to ask him to lie down,
        # increasing the counter of such people by 1.
        elif H[i] > h and W[i] <= h:
            w += H[i]
            k += 1
        #if somebody doesn't fit in both ways,then impossible
        elif H[i] > h and W[i] >h:
            return 1000000005
    #print w*h
    #如果翻转的人数超过一半，则估计不成立
    if k*2 > n:
        return 1000000005
    else:
        #排序
        heap.sort()
        while heap and heap[-1]>0:
            k += 1
            if k*2 <= n:
                w -= heap.pop()
            else:
                break
        #print w,heap,h,w*h,k
        return w*h

for h in range(1,1001):
    X = min(X,proces(h))
#res = proces(h,n/2,0)
#print res
print X