题目描述

$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$

输出格式

塔に含まれるブロックの価値の総和の最大値を出力せよ。

题目大意

题目描述

你有 $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$。

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

提示

制約

• 入力はすべて整数である。
• $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$ と積み重ねればよいです。