Beskrivning
Du spelar ett äventyrsspel. Som magiker måste du använda magi för att hantera flera fiender framför dig. Varje fiende har en nivå, vilket är ett heltal mellan $1$ och $n$. En fiende på nivå $i$ har $2^{i-1}$ hälsopoäng.
Du kan använda två sorters trollformler:
- Själsband (Soul Link): förbrukar $m$ mana och applicerar effekten "Själsband" på en fiende. Denna effekt varar tills fienden dör.
- Attack (Attack): förbrukar $1$ mana och gör $1$ skada på alla fiender med effekten "Själsband", dvs. minskar deras hälsa med $1$. Så fort en fiendes hälsa sjunker till $0$ dör fienden, och du får $m$ mana som belöning.
Bland fienderna framför dig finns det $a_i$ fiender på nivå $i$. Du får använda de två trollformlerna hur många gånger som helst, men din mana får aldrig vara mindre än $0$. Vad är den minsta startmana du behöver för att besegra alla fiender?
Indata
Den första raden innehåller ett heltal $T$ ($1 \le T \le 500$), som anger antalet testfall.
För varje testfall innehåller den första raden två heltal $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), som representerar den maximala fiendenivån respektive manakostnaden för Själsband.
Den andra raden innehåller $n$ positiva heltal. Det $i$-te heltalet $a_i$ anger antalet fiender på nivå $i$.
För varje testfall garanteras det att $0 \le a_i \le 10^9$ och $\sum_{i=1}^n a_i > 0$.
Utdata
För varje testfall, skriv ut en rad som innehåller ett heltal som anger den minsta startmana som krävs för att besegra alla fiender.
Exempel
Indata 1
2 5 7 5 2 4 1 2 6 4 1 1 4 5 1 4
Utdata 1
34 48
Anmärkning
Förklaring till det första testfallet:
Från början finns det 14 fiender med hälsovärdena 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.
Med 34 mana från början, applicera först Själsband på fienderna med hälsa 1, 1, 1, 1, vilket lämnar 6 mana kvar.
Attackera en gång, så blir fiendernas hälsa 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Fyra fiender dör, vilket lämnar 33 mana kvar.
Applicera Själsband på fienderna med hälsa 1, 2, 2, 4, vilket lämnar 5 mana kvar.
Attackera en gång, så blir fiendernas hälsa 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. En fiende dör, vilket lämnar 11 mana kvar.
Applicera Själsband på fienden med hälsa 4, vilket lämnar 4 mana kvar.
Attackera en gång, så blir fiendernas hälsa 0, 0, 2, 3, 4, 4, 8, 16, 16. Två fiender dör, vilket lämnar 17 mana kvar.
Applicera Själsband på fienderna med hälsa 4, 16, vilket lämnar 3 mana kvar.
Attackera två gånger, så blir fiendernas hälsa 0, 1, 2, 4, 8, 14, 16. En fiende dör, vilket lämnar 8 mana kvar.
Applicera Själsband på fienden med hälsa 8, vilket lämnar 1 mana kvar.
Attackera en gång, så blir fiendernas hälsa 0, 1, 4, 7, 13, 16. En fiende dör, vilket lämnar 7 mana kvar.
Attackera en gång, så blir fiendernas hälsa 0, 4, 6, 12, 16. En fiende dör, vilket lämnar 13 mana kvar.
Applicera Själsband på fienden med hälsa 4, vilket lämnar 6 mana kvar.
Attackera fyra gånger, så blir fiendernas hälsa 0, 2, 8, 16. En fiende dör, vilket lämnar 9 mana kvar.
Applicera Själsband på fienden med hälsa 16, vilket lämnar 2 mana kvar.
Attackera två gånger, så blir fiendernas hälsa 0, 6, 14. En fiende dör, vilket lämnar 7 mana kvar.
Attackera sex gånger, så blir fiendernas hälsa 0, 8. En fiende dör, vilket lämnar 8 mana kvar.
Attackera åtta gånger, så dör alla fiender, vilket lämnar 0 mana kvar.