AT_arc226_b.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.

有编号为 $1,2,\dots,N$ 的 $N$ 个袋子。此外，对每个 $i=0,1,\dots,M-1$，存在 $A_i$ 个重量为 $2^i$ 的包裹。总共共有 $A_0+A_1+\dots+A_{M-1}$ 个包裹。

每个包裹恰好放入一个袋子中。某些袋子可能为空。

对于每个袋子，其中所有包裹的重量之和称为该袋子的重量。

求这 $N$ 个袋子的重量的最大值的最小可能值。

你将收到 $T$ 组测试数据；请分别求解每组数据。

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}$

输入从标准输入给出，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例的格式如下：

$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.

输出 $T$ 行。

第 $i$ 行应包含第 $i$ 个测试用例中，各袋子重量的最大值的最小可能值。

Sample 1 Explanation:
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.

样例 1 解释：
在第一个测试用例中，重量分别为 $1,2,4$ 的包裹数量依次为 $3,2,1$。

例如，将重量为 $(4,1,1)$ 的包裹放入背包 $1$，将重量为 $(2,2,1)$ 的包裹放入背包 $2$。此时，背包 $1$ 和背包 $2$ 的总重量分别为 $6$ 和 $5$，其最大值为 $6$。

无法使所有背包的总重量最大值不超过 $5$。

约束条件

• $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$。
• 所有输入值均为整数。