Background

{{Country L is about to go to war with Country I.}}

Problem Description

{{As the saying goes: "Know yourself and know your enemy, and you will never be defeated in a hundred battles." The commander of Country L wants to send spies to Country I, so the task of selection falls on you.

You now have $N$ candidates. Each person has the following data: $A$ (how much intelligence they can obtain), $B$ (how poor their disguise capability is), and $C$ (the salary they demand). The enemy's counterintelligence capability is known to be $M$ (that is, the sum of $B$ for all selected people must be less than or equal to $M$), and you have $X$ units of money. What is the maximum amount of intelligence you can obtain?}}

Input Format

{{The first line contains three integers $N, M, X$ representing the total number of candidates, the enemy's reconnaissance capability, and the total amount of money.

From the second line to the $(N + 1)$-th line, each line contains three integers $A_i, B_i, C_i$, indicating the intelligence the $i$-th person can obtain, how poor their disguise is, and the salary they demand.}}

Output Format

{{Output a single integer representing the total amount of intelligence that can be obtained.}}

3 10 12
10 1 11
1 9 1
7 10 12

11

Hint

{{For $100\%$ of the testdata, $1 \le N \le 100$, $1 \le M \le 1000$, and $1 \le X \le 1000$.}}

Translated by ChatGPT 5