该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

机器人工厂Pro

题目描述

有一个由头部和身体组成的机器人。该机器人有 $N$ 种可同时连接的部件： $1,$ $2,\ldots,$ $N$ 。 $i\ (1\le i\le N)$ 型零件的重量为 $W _i$ 。每个部分连接到头部和连接到身体时的链接感都不同。 $i\ (1\le i\le N)$ 型部件与头部相连时的链接感为 $H _i$ ，与身体相连时的链接感为 $B_ i$ 。

如果头部的重量大于身体的重量，机器人就会倒下。这里，头部的重量和身体的重量分别是连接在头部或身体上的部件重量之和。

小明希望在机器人上安装所有 $N$ 种零件，每种各一个。在不导致机器人倒下的情况下，求所有部件连接后的最大链接值之和。

输入格式

第一行包含一个整数 $N$。

接下来的 $N$ 行，每行包含三个整数 $W_i$，$H_i$ 和 $B_i$。

输出格式

输出在不导致机器人倾倒的情况下，所有部件连接后的最大链接值总和。

输入输出样例 #1

输入 #1

3
1 41 59
2 65 35
8 97 93

输出 #1

217

说明/提示

限制因素

• $1\le N\le500$
• $1\le W _ i\le500\ (1\le i\le N)$
• $1\le H _ i\le10 ^ 9\ (1\le i\le N)$
• $1\le B _ i\le10 ^ 9\ (1\le i\le N)$
• 所有输入值均为整数。

样例一解释

在身体上安装 $1$ 和 $3$ 型零件，在头部安装 $2$ 型零件，机器人就不会摔倒，链接总和就能达到 $217$ 。

在不导致机器人倒下的情况下，不可能将这些部件连接在一起，也不可能使链接值总和达到 $218$ 或更多，因此输出 "217"。