1387 . Striker的秘密

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

97.8% (181/185)

Submission's AC Ratio

40.5% (308/760)

Tags

CKsum 2008-CKsum-3rd

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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