Міньйони - раса крихітних жовтих створінь. Бути міньйоном це звісно ж круто, але Маша сильніше за них... У розпорядженні у Маші є 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