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
For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 5
For Testdata: 19 ~ 19, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 5
For Testdata: 19 ~ 19, Score: 5
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) |
|---|---|---|---|
| 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 |