Migrated from Lutece 2043 二重打击

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

子辉 刚刚收集好记忆碎片，第二重打击又到来了，魔法包正在崩塌。慌乱之中他必须使用魔法容器圣杯拷贝魔法包里的 $n$ 个记忆碎片。

假设开始拷贝记忆碎片为第 $0$ 秒（时间坐标轴上的原点,以下所说的第 $x$ 秒均是时间坐标轴的点，而不是线段） ，同时圣杯的剩余空间足够大，但是在同一时刻只能拷贝一个记忆碎片的内容，而且不能中断，只能在拷贝完当前记忆碎片后才能开始拷贝另一个记忆碎片， 拷贝第i个记忆碎片需要 $c_i$ 秒 ， 且必须在第 $t_i$ 秒前完成拷贝(即使刚好在第 $t_i$ 秒完成拷贝，也不能算是完整地拷贝了这个记忆碎片)， 否则这个记忆碎片就会被完全删除，只能得到一个拥有混乱记忆的损坏了的记忆碎片，同时子辉知道第 $i$ 个记忆碎片的美好程度为 $v_i$ 。

现在子辉想知道如果按照最优策略来安排拷贝记忆碎片的顺序，他能完整拷贝到圣杯里的记忆碎片的美好程度之和最大是多少。

Input

第一行有一个正整数 $n$ ，表示魔法包里有 $n$ ( $1 \le n \le 100$ ) 个记忆碎片， 第二行到第$n+1$行，每行有3个整数 $c_i$ ( $1\le c_i \le 20$ ) , $t_i$ ( $1 \le t_i \le 2000$ ) , $v_i$ ( $1\le v_i \le 20$ ) 分别表示 拷贝第$i$个记忆碎片需要 $c_i$ 秒 ， 在第 $t_i$ 秒之后这个记忆碎片就已经被完全破坏了 ， 第$i$个记忆碎片的美好程度为 $v_i$ ，

Output

一个整数 $ans$ ，表示在最优策略下，能完整拷贝到圣杯里的记忆碎片的美好程度之和的最大值。

Samples

3
2 4 3
1 2 2
3 4 4

5

Note

最优决策是前1秒拷贝第2个记忆碎片，然后紧接着第2秒到第3秒拷贝第1个记忆碎片，这样的重要程度之和为 2+3 = 5

而如果只拷贝第3个记忆碎片，则只能获得4的总重要程度，显然前一种决策更优。

Resources

2018 UESTC Training for Dynamic Programming