题目描述

小明现在碰上了麻烦 —— 他的房间着火了！

它的房间里有 $n$ 件物品，第 $i$ 件物品的价值是 $p_i$，他必须花费 $t_i$ 秒的时间才能将第 $i$ 件物品从房间里搬出来到外面的安全地带，而且本题中我们知道第 $i$ 件物品会第 $d_i$ 秒的时候突然间燃烧起来，并且变得毫无价值，这也就是说，如果小明无法在 $\lt d_i$ 秒时将第 $i$ 件物品搬出来，第 $i$ 件物品都将会燃烧起来并且变得毫无价值。特别地，如果 $t_i \ge d_i$，那么第 $i$ 件物品就没有被搬出来的必要（因为当 $t_i \ge d_i$ 时，及时一开始就搬第 $i$ 件物品，它仍然会燃烧）。

小明只能一件一件地将物品从房间里搬出来，不考虑除了搬物品以外的其它时间开销。举例来说，如果小明一开始选择先搬第 $a$ 件物品，再搬第 $b$ 件物品，则第 $a$ 件物品将会在第 $t_a$ 秒时被搬出来，而第 $b$ 件物品将会在第 $t_a + t_b$ 秒时被搬出来。

请你帮忙计算小明能够搬出来的物品的最大总价值。

输入格式

第一行，一个整数 $n(1 \le n \le 100)$。

接下来 $n$ 行，每行包含三个整数 $t_i, d_i, p_i$，以空格分隔（$1 \le t_i \le 20, 1 \le d_i \le 2000, 1 \le p_i \le 20$）。

输出格式

输出一个整数，表示能够搬出来的物品的最大总价值。

样例

3
3 7 4
2 6 5
3 7 6

11

2
5 6 1
3 3 5

1

说明/提示

样例解释

样例1：先搬第 $2$ 件物品，再搬第 $3$ 件物品。

样例2：因为 $t_2 = d_2 = 3$，所以第 $2$ 件物品没有搬的必要，所以最优解是只搬第 $1$ 件物品。