题目描述

作为船长的你，现在来到了一个宝岛，宝岛上有银锭、珍珠、金戒指、古玩、字画、钻石等一系列奇珍异宝。每种宝贝有三个属性，分别是重量 $w$、价值 $v$、数量 $s$；遗憾的是，你的船舱载重量有限，所以只能带走一部分宝贝，不然，就会沉船了！ 那么，把哪些宝贝搬进船舱，可以使得总价值最大、并且不超载呢？

输入格式

第一行含 $N$ 种宝物与船舱最大载重M，用空格隔开 $（1≤N≤10^2，1≤M≤10^5）$。 接下来 $N$ 行,每行三个整数 $w、v、s$，分别表示第i种宝物的重量、价值、数量 $（ 1≤w,c,s≤10^3 ）$

输出格式

一个整数，表示在不超载的情况下，可以获得的最高总价值。

3 13
2 4 8
3 7 2
4 10 1

29