P2306 mzc bullied by yyh

The third installment of mzc and djn.

mzc is very rich (just kidding). He has $n$ male servants (those who did the previous two installments know this). But none of this can save him from being bullied by yyh, so he is asking you for help. mzc wants to send male servants to fight yyh, but the total mass he can carry is at most $m$. He wants to know whether their (yes, you read that right) total combat power can defeat yyh. Specifically, select a subset of the $n$ servants so that the total mass does not exceed $m$ and the total combat power is maximized, then determine whether this maximum is at least $k$.

The first line contains three integers $n, m, k$, where $n$ is the number of male servants, $m$ is the maximum total mass he can carry, and $k$ is yyh’s combat power. Then follow $n$ lines. Each line contains two integers $a_i, b_i$, denoting the mass and combat power of the $i$-th male servant.

Output two lines. If the maximum total combat power is greater than or equal to $k$, output `yes`; otherwise, output `no`. On the second line, output the maximum total combat power.

- For $20\%$ of the testdata, $n \le 1000$. - For $100\%$ of the testdata, $n, m \le 10^5$, $0 \le a_i, b_i \le 10$. - Time limit: 1 second. Translated by ChatGPT 5