AT_abc431_d [ABC431D] Robot Customize

有一个机器人，由头部和身体组成。这个机器人有 $N$ 种可以同时安装的零件，分别是类型 $1$、类型 $2$、$\ldots$、类型 $N$。第 $i$ 种零件的重量为 $W_i$。每种零件在安装到头部或身体时带来的**幸福度**不一样。当第 $i$ 种零件安装到头部时的幸福度为 $H_i$，当安装到身体时的幸福度为 $B_i$。 如果头部的总重量大于身体的总重量，机器人就会倒下。这里，头部或身体的重量指的是分别安装在头部或身体上的所有零件的重量之和。 高桥想给机器人安装全部 $N$ 种零件，每种零件各用一个。请你求出在不让机器人倒下的情况下，所有零件幸福度之和的最大值。

输入按如下格式从标准输入读入： > $N$ > $W_1$ $H_1$ $B_1$ > $W_2$ $H_2$ $B_2$ > $\vdots$ > $W_N$ $H_N$ $B_N$

输出在不让机器人倒下的情况下所有零件幸福度之和的最大值。

### 样例解释 1 将第 $1$ 种和第 $3$ 种零件安装到身体上，第 $2$ 种零件安装到头部时，机器人不会倒下，且幸福度总和为 $217$。 无法使机器人在不会倒下的情况下，让幸福度总和达到 $218$ 或更高，因此输出 `217`。 ### 样例解释 2 如果只有一个零件，若不安装到身体上，机器人就会倒下。注意，头部可以没有任何零件。 ### 样例解释 3 如果头部和身体重量相等，机器人不会倒下。 ### 样例解释 4 注意，答案可能超过 $2^{32}$。 ### 约束条件 - $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)$ - 所有输入均为整数。 由 ChatGPT 5 翻译