題目描述
你緊係玩緊一款冒險遊戲。作為一名法師,你需要用魔法嚟對付眼前嘅若干敵人。每個敵人都有一個等級,等級係介乎 $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 點法力值。