Маша и миньоны
Миньоны — это маленькие желтые существа. Быть миньоном, конечно, здорово, но Маша сильнее их. У Маши есть n миньонов, каждый из которых обладает определенной силой и выносливостью.
Филипп попросил Машу предоставить ему отряд миньонов. Группа миньонов считается отрядом, если минимальная сила среди них не меньше среднего арифметического их выносливостей. Также считается, что пустая группа миньонов образует отряд.
Задание
Напишите программу, которая по данным о миньонах определит максимальное количество миньонов, которые могут образовать отряд для Филиппа.
Входные данные
Первая строка файла minions.in содержит одно целое число n (1 ⩽ n ⩽ 5*10^4) — количество миньонов у Маши. В следующих n строках содержатся пары целых чисел a[i], b[i] (1 ⩽ a[i], b[i] ⩽ 10^9) — сила и выносливость i-го миньона соответственно.
Выходные данные
Выходной файл minions.out должен содержать одно целое число — максимальное количество миньонов, которые могут образовать отряд из тех, что есть у Маши.
Примеры
Оценивание
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
|---|---|---|---|
0 | 0 | Тесты из условия | - |
1 | 17 | 1 ⩽ n ⩽ 18, 1 ⩽ | 0 |
2 | 8 | Все значения сил миньонов равны | - |
3 | 5 | Все значения выносливостей миньонов равны | - |
4 | 16 | 1 ⩽ n ⩽ 200 | 0, 1 |
5 | 18 | 1 ⩽ | 0, 1 |
6 | 36 | Без дополнительных ограничений | 0, 1, 2, 3, 4, 5 |