Masha and Minions

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Masha has $N$ minions. Each minion has two characteristics: power $a$ and endurance $b$. Masha thinks that a nonempty set of minions $\{m_1, m_2, \dots, m_k\}$ with characteristics $(a_{m_1},b_{m_1}), (a_{m_2},b_{m_2}), \dots, (a_{m_k},b_{m_k})$ is *good* if the mean endurance of this set doesn't exceed the minimum power in it, i.e. if $min(a_{m_1}, a_{m_2}, \dots, a_{m_k}) \ge (b_{m_1}+b_{m_2}+\dots+b_{m_k}) / k$. Masha would like to choose a good subset of her minions and give these minions to Mark. Your task is to calculate the maximum number of minions Masha can give to Mark. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The following $N$ lines describe minions. Each of these lines contains two spaceseparated integers $a$ and $b$ denoting the power and endurance of one minion. ### Output For each test case, print a single line containing one number — the size of the largest good set of minions, or $0$ if no such set exists. ### Constraints  $1 \le T \le 1,000$  $1 \le N \le 4\cdot10^5$  $1 \le a, b \le 10^9$  the sum of $N$ for all test cases does not exceed $4\cdot10^5$ ### Example Input ``` 2 3 1 4 3 3 2 1 2 3 5 1 4 ``` ### Example Output ``` 2 0 ``` ### Explanation **Example case 1:** The set of minions $\{2, 3\}$ is good, since $\mathrm{min}(3,2) \ge (3+1)/2$. **Example case 2:** There is no nonempty good subset of minions.Author:  barenuz 
Editorial  https://discuss.codechef.com/problems/MINIONS 
Tags  barenuz, cook95, medium, mgch, segmenttree 
Date Added:  13062018 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions