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 $*w*_{*i*}$ pixels wide and a $*h*_{*i*}$ pixels high rectangle. But also, each person can lie down for the photo, and then he will occupy a $*h*_{*i*}$ pixels wide and a $*w*_{*i*}$ 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 $*w*_{*i*}, *h*_{*i*}$ ($1 ≤ *w*_{*i*}, *h*_{*i*} ≤ 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.