挑选原石

背包dp

题目描述

有 $n$ 个「套餐」，第 $i$ 套餐需要 $w_i$ 的摩拉来交换 $v_i$ 的原石，这个套餐一共有 $c_i$ 份。旅行者使用了他的元素力，因此他抢在了最前面。由于出门时，旅行者根本没有带多少摩拉，因此他只剩下了 $m$ 元的摩拉。

旅行者还有强迫症，他必须把身上仅有的 $m$ 元摩拉全部花完，并且得到的数量最多。请问他最多能够得到多少原石？

输入格式

• 第 $1$ 行：$n,m$；
• 接下来 $n$ 行：第 $i$ 行输入 $w_i,v_i,c_i$。

输出格式

输出旅行者最多能够得到多少原石。如果他不能把所有的摩拉花完，输出 -1。

提示说明

• $1\le n,m\le n\times m\le 4\times 10^8$；
• $1\le n,m\le 10^6$；
• $1\le w_i,v_i,c_i\le 10^5$。

本题数据较大，非 c++ 选手请退出。作者已亲测，不开 O2 能用暴力卡过，看你怎么卡。