All submissions for this problem are available.### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK109/hindi/WARRIORS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK109/mandarin/WARRIORS.pdf), [Russian](http://www.codechef.com/download/translated/COOK109/russian/WARRIORS.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK109/vietnamese/WARRIORS.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK109/bengali/WARRIORS.pdf) as well. You are a warrior and you have to fight $N$ enemy warriors (numbered $1$ through $N$) one by one, in any order you choose. You have to win as many of these fights as possible. Each warrior has some amount of power, which changes when the warrior fights. For each $i$, the $i$-th enemy warrior has power $P_i$. When you have power $x$ and you fight an enemy warrior with power $y$, the following happens: - if $x \gt y$, you kill the enemy warrior and your power changes to $2(x-y)$ - otherwise (if $x \le y$), the enemy warrior kills you You should answer $Q$ queries. In each query, you are given your initial power $X$ and you should find the maximum number of warriors you can kill if you are starting with power $X$. ### 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 two space-separated integers $N$ and $Q$. - The second line contains $N$ space-separated integers $P_1, P_2, \ldots, P_N$. - $Q$ lines follow. Each of these lines contains a single integer $X$ describing a query. ### Output For each query, print a single line containing one integer — the maximum number of warriors you can kill. ### Constraints - $1 \le T \le 10$ - $1 \le N, Q \le 10^5$ - $1 \le P_i \le 10^9$ for each valid $i$ - $1 \le X \le 10^9$ ### Example Input ``` 1 3 4 1 2 1 10 2 3 1 ``` ### Example Output ``` 3 2 3 0 ```
|Tags||cook109, erfaniaa, greedy, medium, precision, taran_1407|
|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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.