Description
Vous jouez à un jeu d'aventure. En tant que mage, vous devez utiliser la magie pour affronter plusieurs ennemis devant vous. Chaque ennemi a un niveau, qui est un entier compris entre $1$ et $n$. Un ennemi de niveau $i$ possède $2^{i-1}$ points de vie.
Vous pouvez utiliser deux types de sorts :
- Lien d'âme (Soul Link) : consomme $m$ points de mana et applique l'effet « Lien d'âme » à un ennemi. Cet effet dure jusqu'à la mort de cet ennemi.
- Attaque (Attack) : consomme $1$ point de mana et inflige $1$ point de dégâts à tous les ennemis affectés par « Lien d'âme », c'est-à-dire réduit leurs points de vie de $1$. Dès que les points de vie d'un ennemi tombent à $0$, cet ennemi meurt et vous gagnez $m$ points de mana en récompense.
Parmi les ennemis devant vous, il y a $a_i$ ennemis de niveau $i$. Vous pouvez utiliser les deux sorts autant de fois que vous le souhaitez, mais à aucun moment votre mana ne peut être inférieur à $0$. Quel est le mana initial minimum dont vous avez besoin pour vaincre tous les ennemis ?
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 500$), désignant le nombre de cas de test.
Pour chaque cas de test, la première ligne contient deux entiers $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), représentant respectivement le niveau maximum des ennemis et le coût en mana de Lien d'âme.
La deuxième ligne contient $n$ entiers positifs. Le $i$-ème entier $a_i$ désigne le nombre d'ennemis de niveau $i$.
Pour chaque cas de test, il est garanti que $0 \le a_i \le 10^9$ et $\sum_{i=1}^n a_i > 0$.
Sortie
Pour chaque cas de test, affichez une ligne contenant un entier, désignant le mana initial minimum requis pour vaincre tous les ennemis.
Exemples
Entrée 1
2 5 7 5 2 4 1 2 6 4 1 1 4 5 1 4
Sortie 1
34 48
Note
Explication du premier cas de test :
Initialement, il y a 14 ennemis, avec des points de vie de 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.
Avec 34 de mana initialement, appliquez d'abord Lien d'âme aux ennemis ayant 1, 1, 1, 1 de vie, ce qui laisse 6 de mana.
Attaquez une fois : la vie des ennemis devient 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Quatre ennemis meurent, laissant 33 de mana.
Appliquez Lien d'âme aux ennemis ayant 1, 2, 2, 4 de vie, ce qui laisse 5 de mana.
Attaquez une fois : la vie des ennemis devient 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Un ennemi meurt, laissant 11 de mana.
Appliquez Lien d'âme à l'ennemi ayant 4 de vie, ce qui laisse 4 de mana.
Attaquez une fois : la vie des ennemis devient 0, 0, 2, 3, 4, 4, 8, 16, 16. Deux ennemis meurent, laissant 17 de mana.
Appliquez Lien d'âme aux ennemis ayant 4, 16 de vie, ce qui laisse 3 de mana.
Attaquez deux fois : la vie des ennemis devient 0, 1, 2, 4, 8, 14, 16. Un ennemi meurt, laissant 8 de mana.
Appliquez Lien d'âme à l'ennemi ayant 8 de vie, ce qui laisse 1 de mana.
Attaquez une fois : la vie des ennemis devient 0, 1, 4, 7, 13, 16. Un ennemi meurt, laissant 7 de mana.
Attaquez une fois : la vie des ennemis devient 0, 4, 6, 12, 16. Un ennemi meurt, laissant 13 de mana.
Appliquez Lien d'âme à l'ennemi ayant 4 de vie, ce qui laisse 6 de mana.
Attaquez quatre fois : la vie des ennemis devient 0, 2, 8, 16. Un ennemi meurt, laissant 9 de mana.
Appliquez Lien d'âme à l'ennemi ayant 16 de vie, ce qui laisse 2 de mana.
Attaquez deux fois : la vie des ennemis devient 0, 6, 14. Un ennemi meurt, laissant 7 de mana.
Attaquez six fois : la vie des ennemis devient 0, 8. Un ennemi meurt, laissant 8 de mana.
Attaquez huit fois : tous les ennemis meurent, laissant 0 de mana.