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