Problem 1265. -- ACM俱乐部的书架

1265: ACM俱乐部的书架

Time Limit: 10 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 21  Accepted: 5
[Submit][Status][Web Board]

Description

众所周知ACM俱乐部有一个老化的书架,终于一天,TommyTT再也无法忍受这个破旧的书架,于是他找来了Cherish 他们决定做一个新的书架,经过漫长的讨论他们决定做一个三层书架.但由于材料有限他们希望这个书架的面积尽可能的小.现在俱乐部一共有N本书,每本书的高度是h,厚度是t,要都放在这个新书架上,书架的宽是3层书的厚度之和的最大值,书架的高是3层最高的书的和.,求这个新书架的最小面积

Input

有多组输入数据
每组数组第一行是一个整数N代表一共有N本书 30<=N<=70
接下来有N行每行有两个整数hi ti 分别代表每本书的高度和厚度 150 <= hi <= 300 and 5 <= ti <= 30

Output

输出最小面积

Sample Input

4
220 29
195 20
200 9
180 30
6
256 20
255 30
254 15
253 20
252 15
251 9

Sample Output

18000
29796

Source

[Submit][Status][Web Board]