eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Як стати призером

Як стати призером

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

До тренера на заняття з підготовки до олімпіади ходить n школярів. Для кожного зі школярів задано два параметри: початковий умовний досвід a[i] та умовний інтелект b[i].

Кажне заняття побудовано так: тренер підходить до якогось школяра і обговорює з ним питання і проблеми, що виникають. У результаті такого обговорення умовний досвід цього школяра зростає на b[i] (тобто чим вищий умовний інтелект школяра, тим більше цей школяр може взяти від спілкування з тренером).

За весь час підготовки до олімпіади тренер може підійти до усіх школярів загалом не більше c разів (він може підходити до різних школярів, може декілька разів підходити до одного і того ж школяра). Для того, щоб школяр став призером олімпіади, на початок олімпіади його умовний досвід повинен бути не менше ніж k.

Напишіть програму, яка обчислить максимальну кількість призерів олімпіади, які зможе підготувати тренер.

Вхідні дані

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

Вихідні дані

Виведіть одне число - найбільшу кількість призерів олімпиади, які встигне підготувати тренер.

Приклад

Вхідні дані #1
3 5 6
1 1
2 1
4 2
Вихідні дані #1
2
Вхідні дані #2
4 10 3
0 1
0 1
0 2
2 0
Вихідні дані #2
3