Masha and the Minions
Minions are small, yellow creatures known for their unique characteristics. While being a minion is undoubtedly cool, Masha is even stronger. She has n minions at her command, each defined by their strength and endurance.
Philip has requested Masha to assemble a squad of minions. A group of minions qualifies as a squad if the minimum strength among them is at least as large as the average of their endurance values. Additionally, an empty group of minions is also considered a squad.
Task
Create a program that, using the provided minion data, determines the largest possible number of minions that can form a squad for Philip.
Input
The first line of the input file minions.in contains a single integer n (1 ⩽ n ⩽ 5*10^4), representing the number of minions Masha has. The next n lines each contain two integers a[i] and b[i] (1 ⩽ a[i], b[i] ⩽ 10^9), which are the strength and endurance of the i-th minion, respectively.
Output
The output file minions.out should contain a single integer, which is the maximum number of minions that can form a squad from those available to Masha.
Scoring
Subtask | Points | Additional Constraints | Required Subtasks |
|---|---|---|---|
0 | 0 | Tests from the condition | - |
1 | 17 | 1 ⩽ n ⩽ 18, 1 ⩽ | 0 |
2 | 8 | All minions have equal strength values | - |
3 | 5 | All minions have equal endurance values | - |
4 | 16 | 1 ⩽ n ⩽ 200 | 0, 1 |
5 | 18 | 1 ⩽ | 0, 1 |
6 | 36 | No additional constraints | 0, 1, 2, 3, 4, 5 |