徐老师的背包问题

文件读写

• 输入文件dp.in
• 输出文件dp.out

限制

• 1000ms
• 64MB

题目描述

徐老师最近刚学习了《背包九讲》

其中有一种《二维背包问题》是这样的：

一共有 $n$ 个物品，每个物品有三种属性：$h,v,w$，分别代表重量，体积和价值

一个背包的属性有两个：$H,V$ 分别表示背包能承受的重量上限 $H$ 和体积上限 $V$，即物品重量之和 $\leq H$，物品体积之和 $\leq V$，问最多能装进背包的物品总价值最大是多少。

这个问题可太简单了，徐老师分分钟就 AC 了，但是徐老师总是有一些神奇的想法

于是他开始思考，如果他拥有的是一个神奇背包会如何呢？

这个神奇背包允许徐老师在开始装物品之前可以选择一个自然数 $x$，使得 $H-x,V+x$，然后再进行物品的选择

现在徐老师想知道，如果他使用的是这个神奇背包，他能装进背包的物品总价值最大是多少？

输入格式

输入第一行包含三个整数 $n,H,V$ 表示一共有 $n$ 个物品，背包重量上限 $H$，体积上限 $V$

接下来 $n$ 行，每行三个整数 $h_i,v_i,w_i$，分别表示第 $i$ 个物品的重量，体积和价值

输出格式

输出一个整数表示最大价值

数据范围

特别的，对于所有数据保证：$1\leq w_i \leq 10^9, 0\leq h_i,v_i \leq 300$

样例输入

5 10 10
0 1 8
2 3 7
4 5 9
10 10 10
5 5 8

样例输出

25

样例解释

徐老师在开始前可以选择 $x=1$，那么背包就会变成 $H=9,V=11$，然后选择 $1,3,5$ 三个物品得到最大价值 $25$