题目内容

太空探险队准备驾驶星舰前往未知星域，需要在出发前给储物舱装载物资。有 $N$ 种物资，储物舱的容量为 $T$。每种物资都有最大可携带的数量，且每个物品都有固定的价值和体积。

你需要决定每种物资携带多少个，使得在不超过储物舱总容量的前提下，携带物资的总价值最大。

数据范围：物资种类数 $N \le 100$，货舱总容量 $T \le 1000$。每种物资的最大个数、单个价值和单个体积均为不超过 100 的正整数。

输入描述

第一行包含两个整数 n 和 t，分别表示物资种类数和货舱总容量。 接下来 n 行，每行包含三个整数 a_i, v_i, w_i，分别表示第 i 种物资的最大数量、单个价值和单个体积。

输出描述

输出一个整数，表示在容量限制下能获得的最大总价值。

样例1

输入

1 10
2 5 5

输出

10

说明

只有 1 种物资，容量为 10。该物资最多携带 2 个，每个价值 5，体积 5。选择携带全部 2 个，总体积为 $2 \times 5 = 10$，总价值为 $2 \times 5 = 10$，恰好用完容量，是最大价值。

样例2

输入

3 15
2 10 7
3 6 4
1 12 8

输出

22

样例3

输入

2 0
5 10 3
3 7 2

输出

0

样例4

输入

4 20
3 15 9
2 20 11
4 7 3
1 30 12

输出

44