题目描述

你有 $n$ 个箱子，其中编号从 $1$ 到 $n$，每个箱子有三个属性，以第 $i$ 个箱子为例，分别是重量 $w_i$，承重能力 $s_i$，价值 $v_i$。

你想建一座塔，因此需要将一些箱子堆叠起来，但是每个箱子必须满足下面的条件：

这个箱子上面的所有箱子重量和要小于等于这个箱子的承重能力。

定义一个塔的价值为它所用的所有箱子的价值和。

最大化这个塔的价值并输出它。

输入格式

第一行给出正整数 $n$。

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

输出格式

输出一行，$1$ 个整数，表示答案。

样例

样例 1 输入

3
2 2 20
2 1 30
3 1 40

样例 1 输出

50

说明与提示

样例解释

最优解为 $20+30=50$。

对于 $30\%$ 的数据，$1 \leq n \leq 20$。

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