P1509 Find, Find, Find a GF

"Find and find and find a GF, find a good GF, have a meal and hold hands, you are my good GF. Goodbye." "Hey, don’t say goodbye..." Qixi... Qixi... For someone like sqybi, a single rookie, the Qixi Festival is so painful... Even though he listens to this song called "Find and Find and Find GF," he still feels bad. To avoid this pain, sqybi decided to find something to do. He went to the organizer of the Qixi mock contest, zmc MM, and asked her to give him a problem-setting task. After several days of pestering, zmc MM finally agreed. However, after getting the task, sqybi found that setting problems is even more boring than being single -\_- ... So he decided to do another thing at the same time to avoid boredom—find himself a GF.

sqybi now has his eye on $n$ MMs. Let’s number them from $1$ to $n$. Treating MM $i$ to a meal costs $rmb[i]$ coins. Trying to persuade MM $i$ to be his GF (let’s call this "chasing" that MM) consumes $rp[i]$ points of "renpin" (rp). For each MM, there is a time needed to win her over, denoted $time[i]$. sqybi guarantees he has enough charm to win over MM $i$ in $time[i]$ time ^\_^. sqybi wants to get as many MMs as possible to be his GFs, that is certain. But he does not want to spend too much time (after all, the Qixi contest problems are not finished), so among all choices that maximize the number of MMs, he wants the total time spent to be minimized. sqybi currently has $m$ coins, and after some effort he has accumulated $r$ rp (he also earns rp by setting problems for this mock contest~~). With these coins and rp, he can chase some MMs. He wants to know the minimum total time he needs when he gets the maximum possible number of MMs. Note that sqybi can only chase one MM at any moment—if he tries to chase two or more MMs at the same time, they will start fighting...

The first line contains $n$, the number of MMs sqybi is interested in. Then there are $n$ lines, describing MMs numbered $1, 2, 3, \ldots , n$. Each line has three integers: $rmb$, $rp$, and $time$. The last line has two integers, $m$ and $r$.

Output a single line with one integer: the minimum total time, under the condition that the number of MMs obtained is maximized.

sqybi says: If only everything in the statement were true... sqybi also says: If he cannot chase any MM at all, then he spends no time (that is, the time spent is $0$). He will use that time to set Qixi contest problems to earn rp... Constraints - For 20 % of the testdata, $1 \le n \le 10$. - For 100 % of the testdata, $1 \le rmb \le 100$, $1 \le rp \le 100$, $1 \le time \le 1000$. - For 100 % of the testdata, $1 \le m, r, n \le 100$. Translated by ChatGPT 5