Problem : 43 - 太空電梯

Problem Statistics

Solved Member: 35　　Submission: 81　　User Tried: 36

Statement:

　　奶牛們準備升空了！為了進入軌道，他們計劃建造一座由各種材料堆成的巨型太空電梯。她們擁有K (1≤K≤400)種型號不同的材料， i型材料的單位長度為hi (1≤hi≤100)，數量為ci (1≤ci≤10)，由於宇宙射線可能危及材料安全，因此規定堆建材料時，每塊i型材料沒有任何一部分超過ai (1≤ai≤40000)。
　　請幫助奶牛們用這些材料堆出盡可能高的太空電梯。

Input:Output:

第一行：一個整數K。
第二行到第K+1行：每行三個整數：hi，ai，ci。第i+1行描述的是第i塊材料的性質。

一個整數H，表示電梯的最高高度。

Sample Input:Sample Output:

3
7 40 3
5 23 8
2 52 6

Source:

USACO 2005 Mar

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	9
2	1000ms	65536kb	9
3	1000ms	65536kb	9
4	1000ms	65536kb	9
5	1000ms	65536kb	9
6	1000ms	65536kb	9
7	1000ms	65536kb	9
8	1000ms	65536kb	9
9	1000ms	65536kb	9
10	1000ms	65536kb	9
11	1000ms	65536kb	10