1387 . Striker的秘密

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

99.2% (132/133)

Submission's AC Ratio

41.4% (230/555)

Tags

CKsum 2008-CKsum-3rd

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

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
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11
11 10000 65536 262144 12
12 10000 65536 262144 13
13 10000 65536 262144 14
14 10000 65536 262144 15
15 10000 65536 262144 16
16 10000 65536 262144 17
17 10000 65536 262144 18
18 10000 65536 262144 19
19 10000 65536 262144 20
Submit
Status
Ranklist
Back to Top