406028: GYM102219 K Help The Support Lady

Nina works as an IT support in a software company and always busy. The biggest issue she is facing is that sometimes she misses some deadlines. In their team the time needed to finish each customer request is estimated based on experience, $$$1 ≤ x ≤ 10^{5}$$$. The moment a request is submitted, she has double of the estimated time to respond to the request, $$$2x$$$. Meaning if the request $$$A$$$ was submitted at $$$12 pm$$$ and takes $$$2$$$ hours to finish, she can wait $$$2$$$ hours and then work on it for $$$2$$$ hours and still finish the job on time, by $$$4$$$ pm and the customer would be satisfied.

Sometimes there is not enough capacity and she has to pick up a lot of requests, and it is expected to miss some deadlines. But she needs your help, to see if arrange correctly what are the maximum requests she can finish before their deadlines.

Let's assume that she has the list of the requests and their deadline immediately as she starts working every day and she doesn't take any break until she is done with all of them.

The first line contains integer $$$m$$$ $$$(1 ≤ m ≤ 20)$$$. Number of cases.

The second line contains integer $$$n$$$ $$$(1 ≤ n ≤ 10^{5} )$$$. Number of the requests.

The last line contains $$$n$$$ integers $$$t_{i}$$$ $$$(1 ≤ t_{i} ≤ 10^{9} )$$$, separated by spaces. Estimated time each request should be responded so the customer would be happy.

Print the case number and a single number - the maximum number of satisfied customer for each case.

1
5
15 2 1 5 3

Case #1: 4

If she responds to the request with this order $$$1$$$, $$$2$$$, $$$3$$$, $$$5$$$, $$$15$$$, the only customer with the request that requires $$$5$$$ hours wouldn't be happy.