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