Group Photo 2 (online mirror version)

题意翻译

很多年过去了，有n个朋友在一次派对中相聚。从他们上一次相聚到现在，科技已经飞速发展，可以延时摄影的相机已经出现，现在已经没有必要让一个人在照相机前照相，那样会使得他不在这个照片当中。 简单来说，拍照过程如下：每一个人在照片中都会占一个矩形像素：第i个人所占的宽度为w[i],高度为h[i] .但是，每一个人可以在拍照时躺下，那么第i个人躺下所占的宽度为h[i],高度为w[i]，（就是高和宽反过来了） 整张照片的大小为W*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

3
10 1
20 2
30 3

输出样例 #1

180

输入样例 #2

3
3 1
2 2
4 3

输出样例 #2

21

输入样例 #3

1
5 10

输出样例 #3

50