Маша і міньйони
Міньйони - раса крихітних жовтих створінь. Бути міньйоном це звісно ж круто, але Маша сильніше за них... У розпорядженні у Маші є 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.. 0
2...... 8...... Значення сил усiх мiньйонiв рiвнi -
3...... 5...... Значення витривалостей усiх мiньйонiв рiвнi -
4...... 16..... 1 ⩽ n ⩽ 200 0, 1
5...... 18..... 1 ⩽ a[i] , b[i] ⩽ 50 0, 1
6...... 36..... Без додаткових обмежень 0, 1, 2, 3, 4, 5