1387 . Striker的秘密
TopCoder
Tags
Description
Striker到底是如何增強魔力的呢？
原來製造的宮藤博士利用了一種神奇的礦物”櫻石”，使得魔女們對於魔法的振幅發生改變，魔力增加越多，則代表魔力增幅值越強。
但是由於要兼顧飛行的特性，所以每組Striker能搭載的”櫻石”有重量上的限制，所以要如何放置才能使得魔力增幅值達到最大，成了很重要的議題。
現在博士有n種”櫻石”，每種的重量是Wi，魔力增幅值為Mi，但是只有Ci個，要如何放置才能達到最好的效果呢？
Input Format
本題只有一筆測試資料
第一行有一個數字n，代表博士有n種”櫻石”(1<=n<=50)
第二行開始有n行，每行有三個數字Wi,Mi,Ci以空白隔開，代表此種櫻石的重量、魔力增幅值、數量(1<=Wi,Mi,Ci<=100)
最後一行有一個數字T，代表Striker所能搭載的最大上限。 (1<=T<=10000)
Output Format
請輸出一個數字k代表能達到的最大魔力增幅值
Sample Input
5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
15
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
15
Sample Output
15
Hints
Problem Source
原TIOJ1387 / 快樂暑假營第三次練習比賽。
Problem Setter：hallogameboy
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 5 |
| 2 | 1 | 5 |
| 3 | 2 | 5 |
| 4 | 3 | 5 |
| 5 | 4 | 5 |
| 6 | 5 | 5 |
| 7 | 6 | 5 |
| 8 | 7 | 5 |
| 9 | 8 | 5 |
| 10 | 9 | 5 |
| 11 | 10 | 5 |
| 12 | 11 | 5 |
| 13 | 12 | 5 |
| 14 | 13 | 5 |
| 15 | 14 | 5 |
| 16 | 15 | 5 |
| 17 | 16 | 5 |
| 18 | 17 | 5 |
| 19 | 18 | 5 |
| 20 | 19 | 5 |
Testdata and Limits
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
|---|---|---|---|---|
| 0 | 10000 | 65536 | 262144 | |
| 1 | 10000 | 65536 | 262144 | |
| 2 | 10000 | 65536 | 262144 | |
| 3 | 10000 | 65536 | 262144 | |
| 4 | 10000 | 65536 | 262144 | |
| 5 | 10000 | 65536 | 262144 | |
| 6 | 10000 | 65536 | 262144 | |
| 7 | 10000 | 65536 | 262144 | |
| 8 | 10000 | 65536 | 262144 | |
| 9 | 10000 | 65536 | 262144 | |
| 10 | 10000 | 65536 | 262144 | |
| 11 | 10000 | 65536 | 262144 | |
| 12 | 10000 | 65536 | 262144 | |
| 13 | 10000 | 65536 | 262144 | |
| 14 | 10000 | 65536 | 262144 | |
| 15 | 10000 | 65536 | 262144 | |
| 16 | 10000 | 65536 | 262144 | |
| 17 | 10000 | 65536 | 262144 | |
| 18 | 10000 | 65536 | 262144 | |
| 19 | 10000 | 65536 | 262144 |