Make RUN Great Again

KAIST Clubs Union is a student agency that delegates the university’s club funding based on the club’s activity records. Taein is a member of RUN — the marathon club of KAIST — and has joined the KAIST Clubs Union to make it richer.

There are $N+1$ clubs at KAIST numbered from $1$ to $N+1$. RUN has a number $N+1$. KAIST Clubs Union will assign the scores to each club, which is a non-negative integer. A club’s rank is then defined as $(\text{Number of clubs with a higher score than itself}) +1$. Note that there can be multiple clubs with the same rank. The funding opportunities for the club will be better if a club’s rank is lower.

Taein wishes to fabricate the scores in favor of RUN. Currently, every club except the RUN has their scores determined — for each $1\le i\le N$, club $i$ has a score of $a_i$. Taein can change each club’s score under the following conditions:

• Each club’s score should not increase after Taein’s change.
• Each club’s score must be a non-negative integer after Taein’s change.
• If Taein reduces the club $i$’s score by $T$, the KAIST Clubs Union’s skepticism factor will increase by $T\times b_i$, where $b_i$ is an integer decided for each club based on their influence and information gathering skills.
• The total skepticism factor should be less than $K$. If it is at least $K$, it will trigger an internal investigation, which might cause trouble for Taein.

After the fabrication, Taein will fill in the score for RUN, which will finish the funding delegation process.

To avoid suspicion, Taein wishes to keep the score for RUN as low as possible while keeping the rank small enough for all needed funds. You should find the lowest possible initial score for RUN, such that the final rank of RUN is at most $X$, and there exists a fabrication scheme that raises the skepticism factor by less than $K$. Since RUN is a club as well, this score has to be a non-negative integer as well.

The first line contains $N,K,X$, separated by spaces.

The $i$-th of the next $N$ lines contains $a_i$ and $b_i$, separated by a space.

Print the lowest possible initial score for RUN, such that the final rank of RUN is at most $X$, and there exists a fabrication scheme that raises the skepticism factor by less than $K$. Since RUN is a club as well, this score has to be a non-negative integer as well.

• $1\leq N\leq 10^{5}$
• $1\leq K\leq 10^{18}$
• $1\leq X\leq N+1$
• $0\leq a_{i}\leq 10^{6}$
• $1\leq b_{i}\leq 10^{6}$