Problem Description

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

Input Format

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

Output Format

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

3 13
2 4 8
3 7 2
4 10 1

29