1387 . Striker的秘密
TopCoder
Tags
Description
Striker 到底是如何增強魔力的呢？
原來製造的宮藤博士利用了一種神奇的礦物「櫻石」，使得魔女們對於魔法的振幅發生改變，魔力增加越多，則代表魔力增幅值越強。
但是由於要兼顧飛行的特性，所以每組 Striker 能搭載的「櫻石」有重量上的限制，所以要如何放置才能使得魔力增幅值達到最大，成了很重要的議題。
現在博士有 $n$ 種「櫻石」，每種的重量是 $w_i$，魔力增幅值為 $m_i$ ，但是只有 $c_i$ 個，要如何放置才能達到最好的效果呢？
Input Format
本題只有一筆測試資料
第一行有一個數字 $n$ ，代表博士有 $n$ 種「櫻石」。 $(1 \le n \le 50)$
第二行開始有 $n$ 行，每行有三個數字 $w_i, m_i, c_i$ 以空白隔開，代表此種櫻石的重量、魔力增幅值、數量。 $(1 \le w_i, m_i, c_i \le 100)$
最後一行有一個數字 $T$ ，代表 Striker 所能搭載的最大上限。 $(1 \le T \le 10000)$
Output Format
請輸出一個數字，代表能達到的最大魔力增幅值
Sample Input 1
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 1
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 |