Masha and the Minions#8364
Minions are small, yellow creatures. While being a minion is certainly fun, Masha is even stronger than them. She has minions, each characterized by their strength and endurance.
Philip has asked Masha to assemble a squad of minions for him. A group of minions is considered a squad if the minimum strength among them is not less than the arithmetic mean of their endurance values. An empty group of minions is also considered a squad.
Write a program that, given the information about Masha's minions, determines the maximum number of minions that can form a squad for Philip.
The first line of the input file minions.in contains one integer (1 \leq n \leq 5\times 10^4), the number of minions Masha has. The next lines each contain two integers a_i and b_i (1 \leq a_i, b_i \leq 10^9) — the strength and endurance of the -th minion.
The output file minions.out must contain a single integer — the maximum number of minions, from those available to Masha, that can form a squad.
Example 1
Example 2
Subtask | Points | Additional Constraints | Required Subtasks |
|---|---|---|---|
0 | 0 | Samples from statement | - |
1 | 17 | 1 \leq n \leq 18, 1 \leq a_i, b_i \leq 50 | 0 |
2 | 8 | All minions have the same strength | - |
3 | 5 | All minions have the same endurance | - |
4 | 16 | 1 \leq n \leq 200 | 0, 1 |
5 | 18 | 1 \leq a_i, b_i \leq 50 | 0, 1 |
6 | 36 | No additional constraints | 0, 1, 2, 3, 4, 5 |