基础物资发放

题目描述

在灾后重建的安置营地里，救援队正在分发生活物资。现在有 $N$ 种物资需要装入一辆负载能力为 $M$ 的卡车。

每种物资的情况如下：

• 第 $i$ 种物资每件的重量为 $w_i$。
• 第 $i$ 种物资每件能提供的救援价值为 $v_i$。
• 第 $i$ 种物资的数量是有限的，共有 $s_i$ 件。

作为调度员，你需要计算在卡车承重范围内，能够带走的物资总价值最大是多少。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示物资种类和卡车承重上限。

接下来的 $N$ 行，每行包含三个整数 $w_i, v_i, s_i$，分别表示第 $i$ 种物资的重量、价值和数量。

输出格式

输出一个整数，表示能够获得的最大总价值。

输入输出样例 #1

输入 #1

2 10
2 4 3
3 5 2

输出 #1

18

样例 1 说明

选择 3 件第 1 种物资（重 6，价值 12）和 1 件第 2 种物资（重 3，价值 5），总重 9，总分 17？ 不，最优方案：选择 2 件第 1 种物资（重 4，价值 8）和 2 件第 2 种物资（重 6，价值 10），总重 10，总分 18。

数据范围

对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le M \le 100$，$1 \le w_{i}, v_{i} \le 100$，$1 \le s_{i} \le 100$。

建议

一刷