eolymp
bolt
Try our new interface for solving problems
Problems

How to become a winner

How to become a winner

Time limit 1 second
Memory limit 128 MiB

n schoolchildren come to the trainer for classes for preparing to Programming Olympiad. For each schoolchild there are two parameters: initial conditional experience a[i] and conditional intelligence b[i].

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 b[i] (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.

Input data

Сначала вводятся натуральные числа n, c, k (1n10^6, 1c10^9, 1k10^9), задающие количество школьников, количество подходов, которые может сделать учитель, и условный опыт, необходимый, чтобы стать призёром олимпиады, соответственно. Далее идёт n пар целых неотрицательных чисел a[i], b[i], задающих начальный условный опыт и условный интеллект каждого школьника. Каждое из чисел a[i] и b[i] не превышает 10^9.

Output data

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

Examples

Input example #1
3 5 6
1 1
2 1
4 2
Output example #1
2
Input example #2
4 10 3
0 1
0 1
0 2
2 0
Output example #2
3