#背包dp ![[daoqi-pic.png]] ## 题目描述 有 $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 能用暴力卡过，看你怎么卡。