不知道为什么总是听到有人说：电流相生，基米！然后不停念叨：我已启动，我已启.....

我说鸡煲最强有没有懂的，我说鸡煲最强有没有懂.......

来自垃圾场的故障机器人，前来评估高塔，它由“头部”和“身体”两部分组成。这个机器人有 $N$ 种不同的零件可以同时安装，分别为：种类 $1$、种类 $2, \dots,$ 种类 $N$，其中种类 $i\ (1 \le i \le N)$ 零件的重量为 $W_i$。

每一个零件安装在头部或身体上时，会产生不同的快乐值：

如果种类 $i\ (1 \le i \le N)$ 零件被安装在头部，快乐值为 $H_i$；如果该零件被安装在身体上，快乐值为 $B_i$。

如果机器人的头部重量严格大于身体的重量，机器人就会摔倒。这里的“头部重量”和“身体重量”分别指安装在对应部位的所有零件的重量之和。

$\rm anxiao$ 想要把全部 $N$ 种零件都安装到机器人上（每种零件恰好安装一个），请在保证机器人不摔倒的前提下，求出所有零件产生的快乐值总和的最大值。

输入格式

第一行包含一个整数 $N（1\le N \le 500）$ ，这个机器人有 $N$ 种不同的零件可以同时安装。

之后的 $N$ 行， 每行给出三个正整数 $W_i,H_i,B_i$ 分别代表零件的重量，零件安装在头部的快乐值和零件安装在身体的快乐值。

其中 $1 \le W_i \le 500\ (1 \le i \le N)$，$1 \le H_i \le 10^9\ (1 \le i \le N)$ ，$1 \le B_i \le 10^9\ (1 \le i \le N)$ 。

输出格式

输出在保证机器人不摔倒的前提下，能够获得的最大快乐值总和。

输入样例1

3
1 41 59
2 65 35
8 97 93

输出样例1

217

输入样例2

20
483 984529882 299667119
372 428935469 104847758
467 709733529 102461200
421 659244277 110859936
231 786224280 773073478
351 334234040 193222121
119 404159408 772024933
302 519596088 432627257
433 910226244 337833733
184 406236461 530198622
335 465203041 353047747
418 656273464 114923636
482 972364803 329650748
453 748321854 169441643
105 138464898 587159653
401 832952051 506021805
403 810916971 468755944
231 798801044 749313343
292 631278033 556088607
366 567211596 374825770

输出样例2

12091388792