The test data for this problem was rigged and has been fixed since the beginning of the contest, with all non-AC solutions having been rejudged. We apologize for the inconvenience.

hewmatt10 has been participating in rated contests recently!

Starting out with ~R~ rating, and ~V~ volatility, he has participated in ~N~ contests in order, with him getting ~a_i~th place out of ~b_i~ participants, for all ~i~ in the range ~[1, N]~.

After participating in a contest, his rating and volatility will update according to the following formulas: \(\newcommand{\floor}[1]{\lfloor #1 \rfloor}\)

\(R_{new} = \floor{500 × \sqrt{\frac{b_i}{a_i}} × \frac{V_{old}}{2000} + R_{old} × \frac{2000 - V_{old}}{2000}}\)

\(V_{new} = \floor{V_{old} + \sqrt{|R_{old} - R_{new}|} - 100}\)

~V_{new} = max(0, min(2000, V_{new}))~

\(\floor{x}\) denotes the ~floor~ symbol. ~|x|~ denotes the absolute value symbol.

Assume that these formulas are used in sequential order.

hewmatt10, as always, is dissatisfied with his results, and is currently trying to abuse his power to rig the contests! A rig can be defined as unrating a contest as a whole, causing the contest to no longer affect his rating at all.

Given all of this information, can you help hewmatt10 figure out the maximum rating that he can gain?

Input Specification

On the first line, three space-separated integers ~N~, ~R~, and ~V~. ~(1 \le N \le 2000)~, \((0 \le R \le 5 × 10^5)\), ~(0 \le V \le 2000)~. The next ~N~ lines contain two space-separated integers ~a_i~ and ~b_i~. ~(1 \le a_i \le b_i \le 10^6)~.

Output Specification

A single integer, representing the maximum rating that hewmatt10 can end up with.

Subtasks

Subtask	Points	Description
1	30	~N \le 15~.
2	70	No further constraints.

Sample Input

4 1200 385
2 100
100 100
25 350
15 50

Sample Output

1682

Explanation

The optimal move is to unrate the second contest and the last contest.

After the first contest, hewmatt10's rating will be 1649 and his volatility will be 306.

After the second contest, hewmatt10's rating will be 1682 and his volatility will be 211.