《传奇人物大爷传记》之大爷找纸巾

题目背景

大爷想上厕所，所以他决定找纸巾

题目描述

大爷精力为V，现有n个人，每个人占用精力为Vi，贡献纸巾可用次数为Wi，每个人要么至多给Mi次纸巾，要么数量无限，在所费精力不超过V的前提下所找到纸巾的可用次数最大值是多少？

输入格式

第1行，两个数N和V。下面N行，每行三个数Vi,Wi,Mi分别表示每个人的占用精力、贡献纸巾可用次数与数量， Mi>=1表示至多取Mi件，Mi=−1表示数量无限。

输出格式

一个数Ans，表示所找纸的可用次数最大值。

样例

样例输入

5 10
2 3 1
3 2 5
2 2 -1
4 2 1
2 4 2

样例输出

15

数据规模与约定

$N \le 30，V \le 200，Mi \le 10$