Description

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

Input Format

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 Format

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.

3 100 100
7 10
6 1
1 2

no
13

Hint

• 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