#P1782. 旅行商的背包
旅行商的背包
题目描述
小帅深信所有问题均可通过多项式时间解决,因此他决定亲身体验一次旅行商的旅程。在出发之前,他购置了一些商品。这些商品共有 种,第 种商品的体积为 ,价格为 ,库存为 。他的背包容量为 。如何装载商品以实现最大收益?作为一名技艺高超的专家,他轻而易举地解决了这个问题。
然而,在出发前,他又收到了一批独特的商品。这些商品共有 件,第 件商品的价格 与分配的体积 之间的关系为:。虽然这是一件好事,但小帅却不知如何处理。于是,他寻求了一位超级专家(即您)的帮助,请您协助解决此问题。
输入格式
第一行三个数 ,如题中所述;
以下 行,每行有三个数 ,如题中所述;
以下 行,每行有三个数 ,如题中所述。
输出格式
仅一行,为最大的价值。
2 1 10
1 2 3
3 4 1
-1 8 -16
10
提示
样例解释
前两种物品全部选走,最后一个奇货分给 的体积,收益为$2 \times 3+4 \times 1+(-1) \times 16+8 \times 4+(-16)=10$。
限制与约定
对于 的数据,,,,,。