問題文
あなたは冒険ゲームをプレイしています。魔法使いであるあなたは、目の前にいる何体かの敵に魔法で対処しなければなりません。各敵にはレベルがあり、レベルは $1$ から $n$ までの整数です。レベル $i$ の敵は $2^{i-1}$ の体力を持っています。
あなたは 2 種類の呪文を使うことができます:
- ソウルリンク (Soul Link):マナを $m$ 消費し、1 体の敵に「ソウルリンク」効果を付与します。この効果はその敵が死亡するまで持続します。
- 攻撃 (Attack):マナを $1$ 消費し、「ソウルリンク」効果がついているすべての敵に $1$ ダメージを与えます(つまり体力を $1$ 減らします)。敵の体力が $0$ になるとその敵は死亡し、報酬としてマナを $m$ 獲得します。
目の前にいる敵のうち、レベル $i$ の敵は $a_i$ 体います。2 種類の呪文は何回でも使えますが、どの時点でもマナが $0$ 未満になってはいけません。すべての敵を倒すために必要な最小の初期マナはいくつですか?
入力
1 行目にはテストケースの数を表す整数 $T$ ($1 \le T \le 500$) が与えられます。
各テストケースについて、1 行目には敵の最大レベルとソウルリンクの消費マナを表す 2 つの整数 $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$) が与えられます。
2 行目には $n$ 個の正の整数が与えられます。$i$ 番目の整数 $a_i$ はレベル $i$ の敵の数を表します。
各テストケースについて、$0 \le a_i \le 10^9$ および $\sum_{i=1}^n a_i > 0$ が保証されます。
出力
各テストケースについて、すべての敵を倒すために必要な最小の初期マナを表す整数を 1 行に出力してください。
入出力例
入力例 1
2 5 7 5 2 4 1 2 6 4 1 1 4 5 1 4
出力例 1
34 48
注記
1 番目のテストケースの説明:
最初、14 体の敵がいて、それぞれの体力は 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16 です。
初期マナ 34 で、まず体力 1, 1, 1, 1 の敵にソウルリンクを付与し、残りマナは 6 になります。
1 回攻撃すると、敵の体力は 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16 になります。4 体の敵が死亡し、残りマナは 33 になります。
体力 1, 2, 2, 4 の敵にソウルリンクを付与し、残りマナは 5 になります。
1 回攻撃すると、敵の体力は 0, 1, 1, 3, 4, 4, 4, 8, 16, 16 になります。1 体の敵が死亡し、残りマナは 11 になります。
体力 4 の敵にソウルリンクを付与し、残りマナは 4 になります。
1 回攻撃すると、敵の体力は 0, 0, 2, 3, 4, 4, 8, 16, 16 になります。2 体の敵が死亡し、残りマナは 17 になります。
体力 4, 16 の敵にソウルリンクを付与し、残りマナは 3 になります。
2 回攻撃すると、敵の体力は 0, 1, 2, 4, 8, 14, 16 になります。1 体の敵が死亡し、残りマナは 8 になります。
体力 8 の敵にソウルリンクを付与し、残りマナは 1 になります。
1 回攻撃すると、敵の体力は 0, 1, 4, 7, 13, 16 になります。1 体の敵が死亡し、残りマナは 7 になります。
1 回攻撃すると、敵の体力は 0, 4, 6, 12, 16 になります。1 体の敵が死亡し、残りマナは 13 になります。
体力 4 の敵にソウルリンクを付与し、残りマナは 6 になります。
4 回攻撃すると、敵の体力は 0, 2, 8, 16 になります。1 体の敵が死亡し、残りマナは 9 になります。
体力 16 の敵にソウルリンクを付与し、残りマナは 2 になります。
2 回攻撃すると、敵の体力は 0, 6, 14 になります。1 体の敵が死亡し、残りマナは 7 になります。
6 回攻撃すると、敵の体力は 0, 8 になります。1 体の敵が死亡し、残りマナは 8 になります。
8 回攻撃すると、すべての敵が死亡し、残りマナは 0 になります。