题目描述

你有 $n$ 个箱子，编号从 $1$ 到 $n$，每个箱子有三个属性，第 $i$ 个箱子有重量 $w_i$、承重能力 $s_i$、价值 $v_i$。

你想要选择一些箱子摞起来（不一定要按照输入的顺序），其中每个箱子的上方所有箱子的重量之和，要小于等于这个箱子的承重能力。

最大化摞起来的箱子的价值之和。

输入格式

第一行一个正整数 $n$。

之后 $n$ 行，每行给定 $w_i,s_i,v_i$。

输出格式

输出一行一个正整数表示答案。

样例 #1 输入

3
2 2 20
2 1 30
3 1 40

样例 #1 输出

50

样例 #1 解释

第一个箱子放在底下，第二个箱子放在上面，第三个箱子不放。

数据范围与约定

本题采用捆绑测试。

• Subtask1: 30pts，保证 $1\le n\le 20$。
• Subtask2: 70pts，无特殊性质。

对于 $100\%$ 的数据，$1\le n\le 1000,1\le w_i,s_i\le 10^4,1\le v_i\le 10^9$。