终于，破解了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝物。这下小FF可发财了。但是这里的宝物实在是太多了，小FF的采集车似乎装不下那么多宝物。看来小FF只能带走其中一部分宝物了。他整理了一下这些宝物的性质：每件宝物都有一个价值和一个重量，并且每件宝物只有一件。当然不对，其实每种宝物都有很多件。每种宝物都有对应的若干件，并且每件同种宝物的价值和重量都是相同的。小FF的采集车最大载重为W，他想知道在载重范围内，最多可以带走多大价值的宝物。

第一行两个整数n和W，分别表示宝物种类数和采集车最大载重。 接下来n行，每行三个整数vi, wi, mi，分别表示第i种宝物的价值、重量和件数。

一个整数，表示最大价值。

n ≤ 100，W ≤ 40000，mi ≤ 10000