AT_arc226_b [ARC226B] Bin-ary Packing

$ 1,2,\dots,N $ の番号がついた $ N $ 個の袋があります。 また、各 $ i=0,1,\dots,M-1 $ について、重さ $ 2^i $ の荷物が $ A_i $ 個あります。 荷物は合計 $ A_0+A_1+\dots+A_{M-1} $ 個です。 全ての荷物を、それぞれいずれか $ 1 $ 個の袋に入れます。空の袋があっても構いません。 各袋について、その袋に入っている全ての荷物の重さの総和を**袋の重量**と呼びます。 $ N $ 個の袋の重量の最大値としてあり得る最小の値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ A_0 $ $ A_1 $ $ \ldots $ $ A_{M-1} $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、袋の重量の最大値としてあり得る最小の値を出力せよ。

### Sample Explanation 1 $ 1 $ 個目のテストケースでは、重さ $ 1,2,4 $ の荷物がそれぞれ $ 3,2,1 $ 個あります。 例えば、袋 $ 1,2 $ に入れる荷物の重さをそれぞれ $ (4,1,1),(2,2,1) $ とします。 このとき、袋 $ 1,2 $ の重量はそれぞれ $ 6,5 $ であり、その最大値は $ 6 $ です。 袋の重量の最大値を $ 5 $ 以下にすることはできません。 ### 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 $ - 全てのテストケースにおける $ M $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数