Skip to content

1431: Knapsack 3 in 1

题目

题目描述

你想去火星探险,但是由于你只买得起经济舱火箭票,因此你只能带 $W$ 克物品。

你认为有 $n$ 种物品对于你的火星之旅非常重要,其中第 $i$ 种每个质量为 $w_i$,你觉得一件这样的物品对你旅行的重要程度是 $v_i$。由于你在地球上只有 $c_i$ 个 $i$ 类物品,因此你也只能携带这么多个。

现在你想最大化重要程度总和,请输出这个最大价值。

Input

请从 stdin 读入。

输入第一行为两个正整数,$n, W ~ (1 \leq n \leq 800, 1 \leq W \leq 10000)$。

接下来 $n$ 行,第 $i$ 行有三个正整数 $w_i, v_i, c_i (1 \leq w_i, v_i \leq 10000, 1 \leq c_i \leq 10 ^ 9)$。

对于 $30$ 分的数据,$c_i = 1$。

另有 $30$ 分的数据,$c_i = 10 ^ 9$。

另有 $30$ 分的数据,$c_i \in \{1, 10 ^ 9\}$。

Output

请输出到 stdout 中。

输出一行一个整数表示答案。

Sample Input

3 4 3 4 1 2 2 1 2 3 1

3 998 999 9999 1000000000 3 4 1000000000 2 2 1000000000 3 998 3 4 300 2 2 30 2 1 30

1 3 2 2 2

Sample Output

5

1330

1279

2

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!