← 返回题目列表

Codeforces · 524/B

B. 记忆照片 - 2(圆形版)

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

很多年过去了,n个朋友在一次聚会上再次相遇。自从上次会议以来,技术已经向前迈进了一步,带有自拍功能的相机已经出现,现在朋友中的任何一个都不需要站在相机旁边,从而不会被拍到照片中。

拍摄过程可以简化如下。在照片中,每个朋友占据一个像素矩形:在站立位置时,第 i 个朋友占据宽度为 wi 像素、高度为 hi 像素的矩形。而且,拍照时,每个人都可以躺下,然后他会占据一个宽度为 hi 像素、高度为 wi 像素的矩形。

整体照片的尺寸为 W × H,其中 W 是所有人体矩形的总宽度,H 是最大高度。朋友们想要确定共享照片可以拥有的最小面积。帮助他们解决这个问题。

输入

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

接下来的 n 行包含两个整数 wi, hi (1 ≤ wi, hi ≤ 1000),表示第 i 个朋友对应的矩形的尺寸。

输出

打印一个整数,该整数等于照片中可以容纳所有朋友的最小可能面积。

示例

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