Roulette

You are a big fan of Korea's biggest rockstar, Koosaga. Koosaga has announced a lottery event offering fans a once-in-a-lifetime chance at a one-on-one meeting.

Koosaga sells $N$ kinds of albums. When you buy the $i$-th album, it costs $A_i$ won and gives you $B_i$ lottery tickets. You can buy multiple copies of the same album.

On the day of the draw, a large roulette wheel with cells containing participant names decides the winner. Every cell has an equal chance of being selected. The number of cells with your name equals the number of lottery tickets you hold.

Koosaga spins the wheel once to pick the winner. By paying $R$ won, you can ask Koosaga to spin the wheel again. You can pay for as many re-spins as you want.

The total number of cells belonging to other participants is $S$. None of them requests a re-spin. Only you request re-spins, when you want to.

Find the strategy that guarantees your win with the minimum expected cost.

The first line contains three space-separated integers $N$, $S$, $R$.

The next $N$ lines each contain two space-separated integers. The $i$-th line contains $A_i$ and $B_i$.

Print a single line containing two space-separated positive integers $X$, $Y$. $\frac{X}{Y}$ must be the minimum expected cost to win, and $X$ and $Y$ must be coprime. It can be proven that the minimum expected cost can be written in this form.

• $1\le N\le 100000$
• $1\le S\le 10^6$
• $1\le R\le 10^6$
• $1\le A_i\le 300$ ($1\le i\le N$)
• $1\le B_i\le 5000$ ($1\le i\le N$)