题目描述

一艘太空舱正在准备长途航行，需要装载一定质量的物资。任务要求总质量至少为 $m$ 千克。

站内仓库提供 $n$ 种必备物资，第 $i$ 种物资的单件质量为 $w_i$ 千克，单件采购成本为 $v_i$ 星币，由于库存有限，最多只能提供 $s_i$ 件。

工程师需要在总质量至少为 $m$ 的前提下，凑齐所需物资，并希望总成本尽可能小。

请你帮他计算最小的总采购成本。

输入格式

第一行两个整数 $n$ 和 $m$ ，表示物品种类数和目标最低质量。

接下来 $n$ 行，每行三个整数 $w_i$ , $v_i$ , $s_i$ ，分别表示单件质量、单件成本、最大供应数量。

一个整数，表示总质量至少为 $m$ 的最小总成本。

保证所有物资全部购买时，总质量至少为 $m$ 。

对于 $30\%$ 的数据， $1\le n\le 20$ ， $s_i=1$ 。

对于 $50\%$ 的数据， $1\le n\le 100$ ， $s_i=1$ 。

对于 $100\%$ 的数据， $1 \le n \le 100$ ， $1 \le m \le 40000$ ， $1 \le w_i, v_i,\ s_i \le 1000$ 。