Description

Xiaohong says: “Xiaoming, you order.” Xiaoming sees $N$ dishes on the menu, with each dish priced at $C_i$. Xiaoming’s preference score for each dish is $X_i$, and Xiaohong’s preference score for each dish is $Y_i$. (Preference scores may be negative.) (Xiaoming: Based on what I know about her, the data I give you won’t be wrong.)

Xiaoming brought $V$ yuan, and the total price of the dishes he orders cannot exceed $V$. (Xiaoming: Of course I’m paying, it makes me look generous.)

Xiaoming wants to make Xiaohong happy, so he wants her total preference score to be as large as possible. Of course, he also needs to consider his own feelings: the total preference score of all ordered dishes for him must be greater than or equal to $0$. (Xiaoming: If I don’t eat well, she’ll feel bad when she sees it.)

Please help Xiaoming write a program to compute the maximum possible total preference score of Xiaohong under the condition that his own total preference score is greater than or equal to $0$. (Xiaoming: Your program must be reliable. I need to make a good impression on her.)

Input Format

The first line contains two positive integers $N$, $V$.

Then follow $N$ lines, each containing three space-separated numbers: a positive integer $C_i$, and integers $X_i$, $Y_i$.

Output Format

One line with one integer: the maximum possible total preference score of Xiaohong under the condition that Xiaoming’s total preference score is greater than or equal to $0$. If this maximum is less than $0$, output $-1$.

4 10
5 -1 3
2 2 2
11 -5 100
3 -3 10

5

Hint

For $10\%$ of the testdata, $N \leq 10$, $V \leq 50$.

For $30\%$ of the testdata, $X_i, Y_i \geq 0$.

For $100\%$ of the testdata, $N \leq 100$, $V \leq 500$, $|X_i| \leq 5$, $|Y_i| \leq 10^3$.

Translated by ChatGPT 5