Delicious Dining Decision

Xiao Ming is ordering dishes for Xiao Hong. There are N dishes available on the menu. Each dish i has a price C_i, Xiao Ming’s liking degree X_i and Xiao Hong’s liking degree Y_i. Note that the liking values can be negative.

Xiao Ming has V money. The total price of the selected dishes should not exceed V because, as he says, "I must be generous." Moreover, while he wants Xiao Hong to enjoy the meal as much as possible (by maximizing the sum of Y), he also wants to ensure that his own total liking (the sum of X) is at least 0. In short: among all subsets of dishes whose total price is at most V and whose total X is nonnegative, find the one that maximizes the total Y value.

Your task is to write a program to help Xiao Ming decide which dishes to order so that under the constraint that his total liking is at least 0, Xiao Hong's total liking is maximized.

Note: The mathematical formulas are in LaTeX format. For example, the dish prices are given by \(C_i\), Xiao Ming's liking by \(X_i\) and Xiao Hong's liking by \(Y_i\).

inputFormat

The first line contains two integers: N V, where N is the number of dishes and V is the total amount of money available.

Then follow N lines, each containing three integers: Ci Xi Yi representing the price of dish \(i\), Xiao Ming's liking score for dish \(i\), and Xiao Hong's liking score for dish \(i\), respectively.

outputFormat

Output a single integer: the maximum total liking score of Xiao Hong that can be achieved under the constraint that the total price does not exceed V and Xiao Ming's total liking score is at least 0.

sample

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

13