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

Маша і міньйони

Маша і міньйони

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Міньйони - раса крихітних жовтих створінь. Бути міньйоном це звісно ж круто, але Маша сильніше за них... У розпорядженні у Маші є n міньйонів, кожен з яких характеризується своїми силою та витривалістю.

Філіп попросив Машу передати йому в розпорядження загін міньйонів. Герої вважають, що група мiньйонiв утворює загiн, якщо мiнiмальне з значень сил цих мiньйонiв бiльше або рiвне середнього арифметичного їх витривалостей. Також вони вважають, що порожня група міньйонів також утворює загін.

####Завдання

Напишіть програму, яка за інформацією про міньонів, визначить максимальну їх кількість, що утворить загін для Філіпа.

Входные данные

Перший рядок файлу minions.in містить єдине ціле число n(1 ⩽ n ⩽ 5*10^4) – кiлькiсть мiньйонiв у розпорядженнi у Машi. У наступних n рядках знаходяться пари цiлих a[i], b[i](1 ⩽ a[i], b[i] ⩽ 10^9) – значення сили та витривалостi мiньйона з номером i вiдповiдно.

Выходные данные

Вихідний файл minions.out повинен містити єдине цiле число — максимальну кiлькiсть мiньйонiв, якi утворюють загiн з тих, якi є в розпорядженнi у Машi.

####Оцінювання

Пiдзадача Бали Додатковi обмеження Необхідні підзадачі0 0 Тести з умови -1 17 1 ⩽ n ⩽ 18, 1 ⩽ a[i] , b[i] ⩽ 50 02 8 Значення сил усiх мiньйонiв рiвнi -3 5 Значення витривалостей усiх мiньйонiв рiвнi -4 16 1 ⩽ n ⩽ 200 0, 15 18 1 ⩽ a[i] , b[i] ⩽ 50 0, 16 36 Без додаткових обмежень 0, 1, 2, 3, 4, 5

Пример

Входные данные #1
3
1 4
3 3
2 1
Выходные данные #1
2
Входные данные #2
2
3 5
1 4
Выходные данные #2
0
Источник XXXI Всеукраїнська олімпіада з інформатики, Миколаїв, 2-6 квітня 2018