← 返回题目列表

AtCoder · awc0103_d

D. 选择纪念品

中文机器翻译题面 查看原题

分数: 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