Knapsack - Рюкзак

How to become a winner

n schoolchildren come to the trainer for classes for preparing to Programming Olympiad. For each schoolchild there are two parameters: initial conditional experience ai and conditional intelligence bi.

Each lesson is organized in the next way: the trainer approaches a student and discusses the questions and problems that arise with him. As a result of this discussion, the conditional experience of this student will increase by bi (that is, the higher the conventional intelligence of the student, the more this student can take from communication with the trainer).

During the preparation for the Olympiad, the coach can approach all students in total no more than c times (he can approach different students, can approach several times to the same schoolboy). In order for the schoolchild to become a prize-winner of the Olympiad, at the start of the Olympiad his conditional experience should be no less than k.

Write a program that will calculate the maximum number of Olympiad winners that a coach can prepare.


Сначала вводятся натуральные числа n, c, k (1n106, 1c109, 1k109), задающие количество школьников, количество подходов, которые может сделать учитель, и условный опыт, необходимый, чтобы стать призёром олимпиады, соответственно. Далее идёт n пар целых неотрицательных чисел ai, bi, задающих начальный условный опыт и условный интеллект каждого школьника. Каждое из чисел ai и bi не превышает 109.


Print the largest number of prize-winners of the Olympiad, that the trainer can prepare.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
3 5 6
1 1
2 1
4 2
Output example #1
Input example #2
4 10 3
0 1
0 1
0 2
2 0
Output example #2