小風正在玩一個塔防遊戲,和一般的塔防遊戲不同,這款遊戲是要藉由建造塔本身來進行防禦。在一個關卡中會提供 $N$ 件材料讓玩家建造塔,第 $i$ 件材料有三種屬性:重量 $w_i$、耐久值 $s_i$、以及防禦度 $v_i$。建造塔的方式就是從這些材料選一些出來從上至下排列蓋成一座塔,蓋塔需要滿足一個重要的條件:
小風希望能蓋出防禦度總和最高的塔,請你幫小風計算防禦度最高可以達到多少。
輸入第一行有一個正整數 $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$ 件材料的三種屬性。
請輸出一個整數,代表防禦度總和的最大值。
3 2 2 20 2 1 30 3 1 40
50
4 1 2 10 3 1 10 2 4 10 1 6 10
40
5 1 10000 1000000000 1 10000 1000000000 1 10000 1000000000 1 10000 1000000000 1 10000 1000000000
5000000000
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
22
AtCoder
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~3 | 範例測資 | 0 |
2 | 0~22 | 無額外限制 | 100 |