超大多重背包

你有N种物品要放在背包里。物品i的价值为vi ，重量为w i​。 您希望找到要放置的物品集，满足：

物品的总价值尽可能大。

这些物品的总重量最多为W，即背包的容量。

对于第i种物品你最多能选择m i​件放入背包中。

求出背包中物品的最大总价值。

输入：

N W

v1 w1 m1

v2 w2 m2

:

vN wN mN

第一行由整数N和W组成。在之后N行中，给出了第i件物品的价值、重量和限制。

输出：

在一行中输出物品的最大总价值。

数据范围：

N : [1, 50]

vi : [1, 50]

wi : [1, 1e9]

mi : [1, 1e9]

W : [1, 1e9]

样例：

4 8

4 3 2

2 1 1

1 2 4

3 2 2

答案：12

2 100

1 1 100

2 1 50

答案：150

5 1000000000

3 5 1000000000

7 6 1000000000

4 4 1000000000

6 8 1000000000

2 5 1000000000

答案：1166666666

呜呜，这到底要怎么优化？