极度冷冻

题目描述

在科幻世界的南极科考站，科学家需要维持一个精密装置的运行状态，该装置恰好需要 $M$ 千瓦时的备用电量。

科考站储备了 $N$ 种型号的能量电池，每种电池的属性如下：

• 单块电池提供的电量 $w_i$。
• 单块电池的价格 $c_i$（消耗的贡献值）。
• 该型号电池的最大储备量 $s_i$。

为了将节省下来的贡献值用于其他科研项目，请你计算出在凑齐恰好 $M$ 千瓦时电量的基础上，最少需要花费多少贡献值。

如果无论如何组合都无法凑齐恰好 $M$ 千瓦时的电量，请输出 "No solution"。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示电池种类和目标电量。

接下来的 $N$ 行，每行包含三个整数 $w_i, c_i, s_i$，分别表示第 $i$ 种电池的电量、价格和量。

输出格式

输出一个整数或字符串。能够满足要求则输出最小价格，否则输出 "No solution"。

输入输出样例 #1

输入 #1

2 10
3 5 3
4 7 2

输出 #1

17

样例 1 说明

3 个 3 型电池重 9，1 个 4 型重 4，无法凑齐 10。 2 个 3 型电池（共重 6，价 10）+ 1 个 4 型电池（重 4，价 7） = 重 10，价 17。

数据范围

对于 $100\%$ 的数据，$1 \le N \le 500$，$1 \le M \le 1000$，$1 \le w_i, c_i \le 1000$，$1 \le s_i \le 1000$。

建议

二刷