TopCoder

User's AC Ratio

83.3% (15/18)

Submission's AC Ratio

38.5% (25/65)

Description

請參考 TIOJ 1387 Striker的秘密

隨著時代在進步,Striker的載重上限以及"櫻石"開採技術有重大突破,你原本的程式已經無法計算了。

請寫一個新的程式解決這個問題吧!

Input Format

本題只有一筆測試資料

第一行有一個數字n,代表博士有n種”櫻石”(1<=n<=100,000)

第二行開始有n行,每行有三個數字Wi,Mi,Ci以空白隔開,代表此種櫻石的重量、魔力增幅值、數量(1<=Wi,Mi,Ci<=1000)

最後一行有一個數字T,代表Striker所能搭載的最大上限。(1<=T<=1,000,000,但是n*T<=10,000,000)

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

原TIOJ1407 / 快樂暑假營第四次練習比賽。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 3
For Testdata: 1 ~ 1, Score: 3
For Testdata: 2 ~ 2, Score: 3
For Testdata: 3 ~ 3, Score: 3
For Testdata: 4 ~ 4, Score: 3
For Testdata: 5 ~ 5, Score: 3
For Testdata: 6 ~ 6, Score: 3
For Testdata: 7 ~ 7, Score: 3
For Testdata: 8 ~ 8, Score: 3
For Testdata: 9 ~ 9, Score: 3
For Testdata: 10 ~ 10, Score: 3
For Testdata: 11 ~ 11, Score: 3
For Testdata: 12 ~ 12, Score: 3
For Testdata: 13 ~ 13, Score: 3
For Testdata: 14 ~ 14, Score: 3
For Testdata: 15 ~ 15, Score: 3
For Testdata: 16 ~ 16, Score: 3
For Testdata: 17 ~ 17, Score: 3
For Testdata: 18 ~ 18, Score: 3
For Testdata: 19 ~ 19, Score: 3
For Testdata: 20 ~ 20, Score: 3
For Testdata: 21 ~ 21, Score: 3
For Testdata: 22 ~ 22, Score: 3
For Testdata: 23 ~ 23, Score: 3
For Testdata: 24 ~ 24, Score: 3
For Testdata: 25 ~ 25, Score: 3
For Testdata: 26 ~ 26, Score: 3
For Testdata: 27 ~ 27, Score: 3
For Testdata: 28 ~ 28, Score: 3
For Testdata: 29 ~ 29, Score: 3
For Testdata: 30 ~ 30, Score: 3
For Testdata: 31 ~ 31, Score: 7
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 900 65536 262144
3 900 65536 262144
4 900 65536 262144
5 900 65536 262144
6 900 65536 262144
7 900 65536 262144
8 900 65536 262144
9 900 65536 262144
10 900 65536 262144
11 900 65536 262144
12 900 65536 262144
13 900 65536 262144
14 900 65536 262144
15 900 65536 262144
16 900 65536 262144
17 900 65536 262144
18 900 65536 262144
19 900 65536 262144
20 900 65536 262144
21 900 65536 262144
22 900 65536 262144
23 900 65536 262144
24 900 65536 262144
25 900 65536 262144
26 900 65536 262144
27 900 65536 262144
28 900 65536 262144
29 900 65536 262144
30 900 65536 262144
31 900 65536 262144