題目描述
你正在玩一款冒險遊戲。作為一名法師,你需要使用魔法來對付眼前的若干敵人。每個敵人都有一個等級,等級是介於 $1$ 到 $n$ 之間的整數。等級為 $i$ 的敵人擁有 $2^{i-1}$ 點生命值。
你可以使用兩種法術:
- 靈魂連結 (Soul Link):消耗 $m$ 點法力值,對一個敵人施加「靈魂連結」效果。該效果持續到該敵人死亡為止。
- 攻擊 (Attack):消耗 $1$ 點法力值,對所有帶有「靈魂連結」效果的敵人造成 $1$ 點傷害,即它們的生命值減少 $1$。一旦某個敵人的生命值降為 $0$,該敵人就會死亡,並且你將獲得 $m$ 點法力值作為獎勵。
在眼前的敵人中,等級為 $i$ 的敵人有 $a_i$ 個。你可以使用這兩種法術任意次,但在任何時候你的法力值都不能小於 $0$。為了擊敗所有敵人,你最少需要多少初始法力值?
輸入格式
第一行包含一個整數 $T$($1 \le T \le 500$),表示測試資料的數量。
對於每組測試資料,第一行包含兩個整數 $n, m$($1 \le n \le 30, 1 \le m \le 10^{18}$),分別表示敵人的最大等級和施放靈魂連結所需的法力值。
第二行包含 $n$ 個正整數。第 $i$ 個整數 $a_i$ 表示等級為 $i$ 的敵人數量。
對於每組測試資料,保證 $0 \le a_i \le 10^9$ 且 $\sum_{i=1}^n a_i > 0$。
輸出格式
對於每組測試資料,輸出一行包含一個整數,表示擊敗所有敵人所需的最小初始法力值。
範例
範例輸入 1
2 5 7 5 2 4 1 2 6 4 1 1 4 5 1 4
範例輸出 1
34 48
備註
第一組測試資料的解釋:
起初,有 14 個敵人,生命值分別為 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16。
初始擁有 34 點法力值,首先對生命值為 1, 1, 1, 1 的敵人施加靈魂連結,剩餘 6 點法力值。
攻擊一次,敵人的生命值變為 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16。四個敵人死亡,剩餘 33 點法力值。
對生命值為 1, 2, 2, 4 的敵人施加靈魂連結,剩餘 5 點法力值。
攻擊一次,敵人的生命值變為 0, 1, 1, 3, 4, 4, 4, 8, 16, 16。一個敵人死亡,剩餘 11 點法力值。
對生命值為 4 的敵人施加靈魂連結,剩餘 4 點法力值。
攻擊一次,敵人的生命值變為 0, 0, 2, 3, 4, 4, 8, 16, 16。兩個敵人死亡,剩餘 17 點法力值。
對生命值為 4, 16 的敵人施加靈魂連結,剩餘 3 點法力值。
攻擊兩次,敵人的生命值變為 0, 1, 2, 4, 8, 14, 16。一個敵人死亡,剩餘 8 點法力值。
對生命值為 8 的敵人施加靈魂連結,剩餘 1 點法力值。
攻擊一次,敵人的生命值變為 0, 1, 4, 7, 13, 16。一個敵人死亡,剩餘 7 點法力值。
攻擊一次,敵人的生命值變為 0, 4, 6, 12, 16。一個敵人死亡,剩餘 13 點法力值。
對生命值為 4 的敵人施加靈魂連結,剩餘 6 點法力值。
攻擊四次,敵人的生命值變為 0, 2, 8, 16。一個敵人死亡,剩餘 9 點法力值。
對生命值為 16 的敵人施加靈魂連結,剩餘 2 點法力值。
攻擊兩次,敵人的生命值變為 0, 6, 14。一個敵人死亡,剩餘 7 點法力值。
攻擊六次,敵人的生命值變為 0, 8。一個敵人死亡,剩餘 8 點法力值。
攻擊八次,所有敵人死亡,剩餘 0 點法力值。