重生之我喜欢背包

你说得对，这是一个背包问题。

​ 小z很喜欢完沙盒游戏，可是他发现，探索完了之后背包总是装不下物品，于是他准备一次尽可能把尽可能多的价值尽可能高的物品带走，当然了，物品个数是有限的，帮帮他吧，会赢吗？

输入/输出

​ 输入n+1行

​ 第一行两个整数 N 和 V ，N 表示物品种类数，V 表示最大容量

​ 之后n行，每行三个整数 v , w , s 分别表示物品体积、价值和个数

​ 输出一行

​ 表示最大价值

友情提示

​ 想必各位都会多重背包问题吧：），但是简单的dp多重背包的范围还是太小了，所以本题需要各位发挥想象力扩大自己的算法能接受的数据范围

测试数据

输入

​	2 8

​	4 100 2

​	2 100 4

输出

​	400

数据范围

对于测试点 1 - 4 ： 0 < N <= 5 0000 , 0 < W <= 5 0000 , 0 <= ∑m <= 10 0000

对于测试点 5 - 10 ： 0 < N <= 80 0000 ， 0 < W <= 5 0000 ， 0 <= ∑m <= 1000 0000 , N * V <=450 0000