题目描述

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

其中有一种“二维背包问题”是这样的：一共有 $n$ 个物品，每个物品有三种属性 $h_i,v_i,w_i$，分别代表重量、体积和价值。

一个背包有两个属性 $H,V$，分别表示背包能承受的重量上限和体积上限。要求所选物品重量之和不超过 $H$，体积之和不超过 $V$，并最大化物品总价值。

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

这个神奇背包允许徐老师在开始装物品之前选择一个整数 $x$，使背包容量变为 $H-x,V+x$，然后再进行物品的选择。选择的 $x$ 需要使两个容量均非负。

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

输入格式

本题采用文件读写。

• 读入文件名：dp.in
• 写出文件名：dp.out

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

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

输出格式

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

样例

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

25

样例说明

例如选择第 $1,2,5$ 三个物品，总重量为 $7$，总体积为 $9$，总价值为 $25$。

数据范围与提示

• 对于所有数据，$0\le h_i,v_i\le300$，$1\le w_i\le10^9$。