Description

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

Input Format

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 Format

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

4
1 2 5
2 1 6
2 2 2
2 2 3
5 5

13

Hint

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