TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Tags

Description

小風正在玩一個塔防遊戲,和一般的塔防遊戲不同,這款遊戲是要藉由建造塔本身來進行防禦。在一個關卡中會提供 $N$ 件材料讓玩家建造塔,第 $i$ 件材料有三種屬性:重量 $w_i$、耐久值 $s_i$、以及防禦度 $v_i$。建造塔的方式就是從這些材料選一些出來從上至下排列蓋成一座塔,蓋塔需要滿足一個重要的條件:

  • 在塔中的每一件材料 $i$,其耐久度 $s_i$ 不小於在該材料上方的所有材料重量總和。

小風希望能蓋出防禦度總和最高的塔,請你幫小風計算防禦度最高可以達到多少。

Input Format

輸入第一行有一個正整數 $N (1 \leq N \leq 1000)$,代表材料的數量。
接下來的 $N$ 行,第 $i$ 行有三個整數 $w_i, s_i, v_i (1 \leq w_i, s_i \leq 10000, 1 \leq v_i \leq 10^ 9)$,分別代表第 $i$ 件材料的三種屬性。

Output Format

請輸出一個整數,代表防禦度總和的最大值。

Sample Input 1

3
2 2 20
2 1 30
3 1 40

Sample Output 1

50

Sample Input 2

4
1 2 10
3 1 10
2 4 10
1 6 10

Sample Output 2

40

Sample Input 3

5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000

Sample Output 3

5000000000

Sample Input 4

8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5

Sample Output 4

22

Hints

Problem Source

AtCoder

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0~22 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 1 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2