/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
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 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 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 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N M
A_0 A_1 \ldots A_{M-1}
出力
T 行出力せよ。
i 行目には i 番目のテストケースについて、袋の重量の最大値としてあり得る最小の値を出力せよ。
入力例 1
4 2 3 3 2 1 1000000 1 0 1 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 188075 10 858153 791486 630853 157728 813993 50047 286602 459270 597406 907405
出力例 1
6 0 549755813888 3805
1 個目のテストケースでは、重さ 1,2,4 の荷物がそれぞれ 3,2,1 個あります。
例えば、袋 1,2 に入れる荷物の重さをそれぞれ (4,1,1),(2,2,1) とします。 このとき、袋 1,2 の重量はそれぞれ 6,5 であり、その最大値は 6 です。
袋の重量の最大値を 5 以下にすることはできません。
Score : 500 points
Problem Statement
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.
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.
Input
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
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 Input 1
4 2 3 3 2 1 1000000 1 0 1 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 188075 10 858153 791486 630853 157728 813993 50047 286602 459270 597406 907405
Sample Output 1
6 0 549755813888 3805
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.