Маша і міньйони#8364
Міньйони — це маленькі жовті істоти. Бути міньйоном, звісно, весело, але Маша сильніша за них. У Маші є міньйонів, кожен з яких характеризується своєю силою і витривалістю.
Філіп попросив Машу зібрати для нього загін міньйонів. Група міньйонів вважається загоном, якщо мінімальна сила серед них не менша за середнє арифметичне їхніх витривалостей. Порожня група міньйонів теж вважається загоном.
Напишіть програму, яка за інформацією про міньйонів визначає максимальну їх кількість, що можуть утворити загін для Філіпа.
Перший рядок вхідного файлу minions.in містить одне ціле число (1 \leq n \leq 5\times 10^4) — кількість міньйонів у Маші. У наступних рядках містяться пари цілих чисел a_i і b_i (1 \leq a_i, b_i \leq 10^9) — сила та витривалість -го міньйона відповідно.
Вихідний файл minions.out має містити одне ціле число — максимальну кількість міньйонів, які можуть утворити загін із тих, що є у Маші.
Приклад 1
Приклад 2
Підзадача | Бали | Додаткові обмеження | Необхідні підзадачі |
|---|---|---|---|
0 | 0 | Тести з умови | - |
1 | 17 | 1 \leq n \leq 18, 1 \leq a_i, b_i \leq 50 | 0 |
2 | 8 | Усі міньйони мають однакову силу | - |
3 | 5 | Усі міньйони мають однакову витривалість | - |
4 | 16 | 1 \leq n \leq 200 | 0, 1 |
5 | 18 | 1 \leq a_i, b_i \leq 50 | 0, 1 |
6 | 36 | Без додаткових обмежень | 0, 1, 2, 3, 4, 5 |