小風正在玩一個塔防遊戲,和一般的塔防遊戲不同,這款遊戲是要藉由建造塔本身來進行防禦。在一個關卡中會提供 $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$ 件材料的三種屬性。
請輸出一個整數,代表防禦度總和的最大值。
AtCoder
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~3 | 範例測資 | 0 |
2 | 0~22 | 無額外限制 | 100 |