Tower
题意翻译
### 题目描述
你有 $n$ 个箱子,编号从 $1$ 到 $n$,每个箱子有三个属性,以第 $i$ 个箱子为例,分别是重量 $w_i$,承重能力 $s_i$,价值 $v_i$。
你想建一座塔,因此需要将一些箱子堆叠起来,但是每个箱子必须满足下面的条件:
- 这个箱子上面的所有箱子重量和要小于等于这个箱子的承重能力。
定义一个塔的价值为它所用的所有箱子的价值和。
最大化这个塔的价值并输出它。
### 输入格式
第一行一个整数 $n$,表示箱子数量。
接下来 $n$ 行,一行三个整数,用来描述这个箱子的三个属性 $w_i,s_i,v_i$。
### 输出格式
一行一个整数,表示塔的最大价值。
### 数据范围
$n \le 10^3, 1 \le w_i, s_i \le 10^4, 1 \le v_i \le 10^9$。
题目描述
[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 $ $ w_1 $ $ s_1 $ $ v_1 $ $ w_2 $ $ s_2 $ $ v_2 $ $ : $ $ w_N $ $ s_N $ $ v_N $
输出格式
塔に含まれるブロックの価値の総和の最大値を出力せよ。
输入输出样例
输入样例 #1
3
2 2 20
2 1 30
3 1 40
输出样例 #1
50
输入样例 #2
4
1 2 10
3 1 10
2 4 10
1 6 10
输出样例 #2
40
输入样例 #3
5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
输出样例 #3
5000000000
输入样例 #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
输出样例 #4
22
说明
### 制約
- 入力はすべて整数である。
- $ 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 $ と積み重ねればよいです。