TopCoder

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

7.1% (1/14)

Description

球主最近看了好多書。包括

"十大你不可不知的人類"
   - 一本精彩絕倫的偉人傳記,其中紀錄的包括卡恩、海恩、黃以文等若干人類。
"三分鐘學會微分方程與線性代數"
   - 某汪老教授出版,但球主並沒有成功想必是資質太低
"UML讓你考試都一百分"
   - 一本愛與友情與嘴砲的優良讀物,堪稱現代書籍中之撒尿牛丸
"園藝大全:如何種出又大又強的蕃茄"
   - 此書開宗明義地寫著: "這是講天份滴",於是球主就不看了
"一千個WA的理由"
   - 著名歌手張鞋友的WA辛酸血淚史
"文字冒險遊戲攻略集"
   - ????

...

從以上我們可以看出球主真的是一個認真好學、熱愛閱讀的文藝青年。

不過最近球主有個煩惱,就是他的書實在太多了,桌上已經完全被堆滿,沒有打鬥塔的空間了。
雖然這樣子使他看起來很認真,但是每次dota的時候滑鼠施展不開而被殺如麻,卻深深困擾著球主。

終於,球主靈機一動,想說: "哦~ 我何不打造個書櫃呢?!"

然而打造書櫃是一回事,要如何打造最省空間的書櫃又是一回事,這個任務深深地困擾著球主。
球主想要打造一個三層的書櫃,這三層不見得要一樣高,但寬度當然是得要一樣寬的。
當然這書櫃必須要能放得下球主的全部n本書才行!
所以想當然爾,除了寬度要夠,每層的高度也要大於等於該層所有書本的高度。
為了美觀,每本書都是直的放進書櫃的 (不可躺著或用其他各種形式)。
而所謂的省空間,就是讓書櫃的"面積"(寬*高)最小,
至於書櫃的"深度"我們無須考慮,因為書櫃深度當然就是至少要所有書本中最寬的那麼深啦!

所以假設球主所有書的編號是從1到n,那麼每本書都有其厚度ti,以及期高度hi
則此問題相當於是我們要把每本書分到書櫃的其中一排,使得

最小。

今給定n本書的高度hi及厚度ti,試問書櫃面積最小為多少?

Input Format

第一行有一個數字t,代表有幾組測資
每組測資的第一行有一個數字n,代表球主總共有幾本書
接下來n行每行有兩個數字hi和ti,代表第i本書的高度和厚度。

3 ≤ N ≤ 70,
150 ≤ hi ≤ 300,
5 ≤ ti ≤ 30.

Output Format

請輸出一個整數,代表書櫃的最小面積。

Sample Input

2
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

Hints

Problem Source

原TIOJ1522 / 2009宵夜盃練習賽II。Problem Setter:kelvin。

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2