分数: 400 分
问题陈述
高桥正在他的旅行目的地的一家纪念品商店购物。店里有 N 的产品类型,其中 i第产品的重量为 w_i 克,满意度值为 v_i,以及库存 c_i 项目。高桥可以从以下网站购买任意数量的每种产品 0 to c_i 包括在内。
Takahashi 希望使他购买的总重量与回程航班托运行李的指定值完全匹配。具体来说,他希望所购买产品的总重量恰好是 S 克。这里,总重量是所有产品的(每个产品的重量)×(购买数量)之和。
判断总重量是否可以准确 S 克。如果可能的话,输出最大的总满意度。这里,总满意度是所有产品的(每个产品的满意度)×(购买数量)之和。如果不可能,则输出 -1.
请注意,选择不购买任何产品(即购买 每个产品的 0 )也是允许的。在这种情况下,总权重和总满意度都是 0.
约束
- 1 \leq N \leq 100
- 1 \leq S \leq 30000
- 1 \leq w_i \leq 30000
- 1 \leq v_i \leq 10^4
- 1 \leq c_i \leq 10^5
- 所有输入值均为整数。
输入
N S w_1 v_1 c_1 w_2 v_2 c_2 \vdots w_N v_N c_N
- 第一行包含产品类型的数量 N 和目标总重量 S,用空格分隔。
- 以下 N 行各包含,对于 i第一个产品,其重量 w_i, 满意 v_i和库存 c_i,用空格分隔。
输出
是否可以准确计算出总重量 S 克,在一行中输出最大总满意度。如果不可能,则输出 -1 一行。
示例输入 1
3 10 2 3 3 3 5 2 5 8 1
示例输出 1
16
示例输入 2
2 7 4 10 1 6 20 1
示例输出 2
-1
示例输入 3
8 100 6 12 5 10 20 3 15 35 4 22 45 2 7 9 10 30 80 1 11 25 6 18 40 3
示例输出 3
240
示例输入 4
20 5000 37 120 100 123 500 30 256 900 20 511 2000 10 1024 4100 4 999 3000 6 75 250 50 48 160 70 300 1000 15 450 1800 8 17 40 200 620 2500 5 840 3100 3 1500 7000 2 2300 9000 1 5 9 1000 199 800 25 333 1200 12 777 2800 4 12000 5000 10
示例输出 4
22067
示例输入 5
1 30000 1 10000 100000
示例输出 5
300000000