Group Photo 2 (online mirror version)

题面翻译

很多年过去了，有 $n$ 个朋友在一次派对中相聚。从他们上一次相聚到现在，科技已经飞速发展，可以延时摄影的相机已经出现，现在已经没有必要让一个人在照相机前照相，那样会使得他不在这个照片当中。

简单来说，拍照过程如下：每一个人在照片中都会占一个矩形像素：第 $i$ 个人所占的宽度为 $w_i$,高度为 $h_i$ .但是，每一个人可以在拍照时躺下，那么第 $i$ 个人躺下所占的宽度为 $h_i$,高度为 $w_i$（就是高和宽反过来了）。

整张照片的大小为 $W\times H$。$W$ 是所有人宽的总和，$H$ 是照片当中最高的那个人的高度。朋友们想让一个能装下他们所有人的照片并且让这张照片的大小尽可能小，并且不能有超过一半以上的人躺下。（如果有超过一半以上的人躺在地上会显得很奇怪，难道不是吗？？） 请帮助他们达到这个要求。

题目描述

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.

输入格式

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.

输出格式

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.

样例 #1

样例输入 #1

3
10 1
20 2
30 3

样例输出 #1

180

样例 #2

样例输入 #2

3
3 1
2 2
4 3

样例输出 #2

21

样例 #3

样例输入 #3

1
5 10

样例输出 #3

50