Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 256 MB 总分: 100 可 Hack ✓
统计

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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.