Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Group Photo 2 (online mirror version)

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMany 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.

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

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2019 04:37:30 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|