AT_dp_x Tower

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_x $ N $ 個のブロックがあります。 ブロックには $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、ブロック $ i $ の重さは $ w_i $ で、丈夫さは $ s_i $ で、価値は $ v_i $ です。 太郎君は、$ N $ 個のブロックのうち何個かを選び、それらを任意の順序で一列に積み重ね、塔を作ることにしました。 このとき、塔は次の条件を満たさなければなりません。 - 塔に含まれる各ブロック $ i $ について、ブロック $ i $ より上に積まれたブロックの重さの総和は $ s_i $ 以下である。 塔に含まれるブロックの価値の総和の最大値を求めてください。

N/A

N/A

### 制約 - 入力はすべて整数である。 - $ 1\ \leq\ N\ \leq\ 10^3 $ - $ 1\ \leq\ w_i,\ s_i\ \leq\ 10^4 $ - $ 1\ \leq\ v_i\ \leq\ 10^9 $ ### Sample Explanation 1 上から順にブロック $ 2,\ 1 $ と積み重ねると、この塔は条件を満たします。 塔に含まれるブロックの価値の総和は $ 30\ +\ 20\ =\ 50 $ となります。 ### Sample Explanation 2 上から順にブロック $ 1,\ 2,\ 3,\ 4 $ と積み重ねればよいです。 ### Sample Explanation 3 答えは 32-bit 整数型に収まらない場合があります。 ### Sample Explanation 4 例えば、上から順にブロック $ 5,\ 6,\ 8,\ 4 $ と積み重ねればよいです。