很多年过去了,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