AT_arc226_b [ARC226B] Bin-ary Packing

There are $ N $ bags numbered $ 1,2,\dots,N $ . Also, for each $ i=0,1,\dots,M-1 $ , there are $ A_i $ packages of weight $ 2^i $ . There are $ A_0+A_1+\dots+A_{M-1} $ packages in total. Every package is put into exactly one of the bags. Some bags may remain empty. For each bag, the sum of the weights of all packages in that bag is called the **weight of the bag**. Find the minimum possible value of the maximum of the weights of the $ N $ bags. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ M $ $ A_0 $ $ A_1 $ $ \ldots $ $ A_{M-1} $

Output $ T $ lines. The $ i $ -th line should contain the minimum possible value of the maximum of the weights of the bags for the $ i $ -th test case.

### Sample Explanation 1 In the first test case, there are $ 3,2,1 $ packages of weight $ 1,2,4 $ , respectively. For example, let the weights of the packages put into bags $ 1,2 $ be $ (4,1,1),(2,2,1) $ , respectively. Then, the weights of bags $ 1,2 $ are $ 6,5 $ , respectively, and the maximum of these is $ 6 $ . It is impossible to make the maximum of the weights of the bags $ 5 $ or less. ### Constraints - $ 1 \le T \le 10^5 $ - $ 1 \le N \le 10^6 $ - $ 1 \le M \le 40 $ - $ 0 \le A_i \le 10^6 $ - The sum of $ M $ over all test cases is at most $ 2 \times 10^5 $ . - All input values are integers.