← 返回题目列表

Codeforces · 529/B

B. 合影2(网络镜像版)

中文机器翻译题面 查看原题

很多年过去了,n个朋友在一次聚会上再次相遇。自上次会议以来,技术已经取得了飞跃性的发展,带有计时器的相机出现了,现在朋友中的一个不必拿着相机站着,因此不再出现在照片中。

简单来说,拍照的过程可以描述如下。每个朋友在照片上占据一个像素矩形:其中第 i 个处于站立状态的朋友占据一个 wi 像素宽、一个 hi 像素高的矩形。而且,每个人都可以躺下拍照,然后他将占据一个 hi 像素宽、wi 像素高的矩形。

总照片的大小为 W × H,其中 W 是所有人物矩形的总宽度,H 是高度的最大值。小伙伴们想求一下,如果不超过n/2个人躺在地上,合影的最小面积是多少(如果超过n/2个先生一起躺在地上就很奇怪了,不是吗?..)

帮助他们实现这一目标。

输入

第一行包含整数 n (1 ≤ n ≤ 1000) — 好友数量。

接下来n行各有两个整数wi,hi (1 ≤ wi, hi ≤ 1000),代表矩形的大小,对应第i个朋友。

输出

打印一个整数,该整数等于包含所有朋友的照片的最小可能面积(如果躺在地上的朋友不超过 n/2)。

示例

输入 #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