P1910 {{Country L's Wartime Spy}}

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

{{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?}}

{{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 a single integer representing the total amount of intelligence that can be obtained.}}

{{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