TopCoder

Thumb giphy  1
實中34th的一個人
要吃巧克力嗎??

User's AC Ratio

98.3% (59/60)

Submission's AC Ratio

37.2% (103/277)

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

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
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