← 返回题目列表

AtCoder · tdpc_knapsack

H. 背包

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

问题陈述

N 东西;i 重量、价值和颜色w_i, v_i, c_i 。斯努克决定在背包里放一些东西。然而,背包中物品的总重量为 W 颜色是 C 必须小于或等于类型。求背包中可放入物品总价值的最大值。

约束

  • 1 ≤ N ≤100
  • 1 ≤ W ≤10000
  • 1 ≤ C ≤ 50
  • 1 ≤ w_i, v_i ≤ 10000
  • 1 ≤ c_i ≤ 50

输入格式

输入是按以下格式从标准输入给出的。
N W C
w_1 v_1 c_1
…
w_N v_N c_N

输出格式

将答案输出在一行。

示例输入 1

4 5 2
1 10 1
1 20 2
1 30 3
10 100 4

示例输出 1

50
您可能想要包括第二个和第三个。 如果满足以下条件,则

示例输入 2

10 20 2
4 5 6
3 3 9
5 2 9
4 1 6
6 8 3
3 7 6
2 4 9
4 7 3
6 5 6
3 2 9

示例输出 2

27