Beskrivelse
Du spiller et eventyrspill. Som magiker må du bruke magi for å håndtere flere fiender foran deg. Hver fiende har et nivå, som er et heltall mellom $1$ og $n$. En fiende på nivå $i$ har $2^{i-1}$ helsepoeng.
Du kan bruke to typer trylleformler:
- Sjelebånd (Soul Link): bruker $m$ mana og påfører effekten «Sjelebånd» på én fiende. Denne effekten varer til fienden dør.
- Angrep (Attack): bruker $1$ mana og gjør $1$ skade på alle fiender med effekten «Sjelebånd», dvs. reduserer helsen deres med $1$. Så snart en fiendes helse faller til $0$, dør fienden, og du får $m$ mana som belønning.
Blant fiendene foran deg er det $a_i$ fiender på nivå $i$. Du kan bruke de to trylleformlene så mange ganger du vil, men manaen din kan ikke på noe tidspunkt være mindre enn $0$. Hva er den minimale startmanaen du trenger for å beseire alle fiendene?
Inndata
Den første linjen inneholder et heltall $T$ ($1 \le T \le 500$), som angir antallet testtilfeller.
For hvert testtilfelle inneholder den første linjen to heltall $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), som representerer henholdsvis det maksimale fiendenivået og manakostnaden for Sjelebånd.
Den andre linjen inneholder $n$ positive heltall. Det $i$-te heltallet $a_i$ angir antallet fiender på nivå $i$.
For hvert testtilfelle garanteres det at $0 \le a_i \le 10^9$ og $\sum_{i=1}^n a_i > 0$.
Utdata
For hvert testtilfelle skal du skrive ut én linje som inneholder et heltall som angir den minimale startmanaen som kreves for å beseire alle fiendene.
Eksempler
Inndata 1
2 5 7 5 2 4 1 2 6 4 1 1 4 5 1 4
Utdata 1
34 48
Merk
Forklaring til det første testtilfellet:
Til å begynne med er det 14 fiender med helseverdiene 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.
Med 34 mana til å begynne med, bruk først Sjelebånd på fiendene med helse 1, 1, 1, 1, slik at det gjenstår 6 mana.
Angrip én gang, så blir fiendenes helse 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Fire fiender dør, og det gjenstår 33 mana.
Bruk Sjelebånd på fiendene med helse 1, 2, 2, 4, slik at det gjenstår 5 mana.
Angrip én gang, så blir fiendenes helse 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Én fiende dør, og det gjenstår 11 mana.
Bruk Sjelebånd på fienden med helse 4, slik at det gjenstår 4 mana.
Angrip én gang, så blir fiendenes helse 0, 0, 2, 3, 4, 4, 8, 16, 16. To fiender dør, og det gjenstår 17 mana.
Bruk Sjelebånd på fiendene med helse 4, 16, slik at det gjenstår 3 mana.
Angrip to ganger, så blir fiendenes helse 0, 1, 2, 4, 8, 14, 16. Én fiende dør, og det gjenstår 8 mana.
Bruk Sjelebånd på fienden med helse 8, slik at det gjenstår 1 mana.
Angrip én gang, så blir fiendenes helse 0, 1, 4, 7, 13, 16. Én fiende dør, og det gjenstår 7 mana.
Angrip én gang, så blir fiendenes helse 0, 4, 6, 12, 16. Én fiende dør, og det gjenstår 13 mana.
Bruk Sjelebånd på fienden med helse 4, slik at det gjenstår 6 mana.
Angrip fire ganger, så blir fiendenes helse 0, 2, 8, 16. Én fiende dør, og det gjenstår 9 mana.
Bruk Sjelebånd på fienden med helse 16, slik at det gjenstår 2 mana.
Angrip to ganger, så blir fiendenes helse 0, 6, 14. Én fiende dør, og det gjenstår 7 mana.
Angrip seks ganger, så blir fiendenes helse 0, 8. Én fiende dør, og det gjenstår 8 mana.
Angrip åtte ganger, så dør alle fiendene, og det gjenstår 0 mana.