Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 256 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Opis

Grasz w grę przygodową. Jako mag musisz użyć magii, aby poradzić sobie z kilkoma stojącymi przed tobą wrogami. Każdy wróg ma poziom będący liczbą całkowitą z przedziału od $1$ do $n$. Wróg na poziomie $i$ posiada $2^{i-1}$ punktów zdrowia.

Możesz używać dwóch rodzajów zaklęć:

  • Więź dusz (Soul Link): zużywa $m$ punktów many i nakłada efekt „Więzi dusz” na jednego wroga. Efekt ten utrzymuje się aż do śmierci tego wroga.
  • Atak (Attack): zużywa $1$ punkt many i zadaje $1$ punkt obrażeń wszystkim wrogom objętym efektem „Więzi dusz”, tj. zmniejsza ich zdrowie o $1$. Gdy zdrowie wroga spadnie do $0$, wróg ten ginie, a ty otrzymujesz $m$ punktów many w nagrodę.

Wśród stojących przed tobą wrogów znajduje się $a_i$ wrogów na poziomie $i$. Możesz używać obu zaklęć dowolną liczbę razy, ale w żadnym momencie twoja mana nie może spaść poniżej $0$. Jaka jest minimalna początkowa ilość many potrzebna do pokonania wszystkich wrogów?

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 500$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera dwie liczby całkowite $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), oznaczające odpowiednio maksymalny poziom wroga oraz koszt many zaklęcia Więź dusz.

Drugi wiersz zawiera $n$ dodatnich liczb całkowitych. $i$-ta liczba całkowita $a_i$ oznacza liczbę wrogów na poziomie $i$.

Dla każdego przypadku testowego gwarantuje się, że $0 \le a_i \le 10^9$ oraz $\sum_{i=1}^n a_i > 0$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający liczbę całkowitą oznaczającą minimalną początkową ilość many wymaganą do pokonania wszystkich wrogów.

Przykłady

Wejście 1

2
5 7
5 2 4 1 2
6 4
1 1 4 5 1 4

Wyjście 1

34
48

Uwaga

Wyjaśnienie dla pierwszego przypadku testowego:

Początkowo jest 14 wrogów o wartościach zdrowia 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.

Mając na początku 34 punkty many, najpierw nałóż Więź dusz na wrogów o zdrowiu 1, 1, 1, 1, po czym zostaje 6 punktów many.

Zaatakuj raz — zdrowie wrogów zmienia się na 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Czterech wrogów ginie, zostaje 33 punkty many.

Nałóż Więź dusz na wrogów o zdrowiu 1, 2, 2, 4, zostaje 5 punktów many.

Zaatakuj raz — zdrowie wrogów zmienia się na 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Jeden wróg ginie, zostaje 11 punktów many.

Nałóż Więź dusz na wroga o zdrowiu 4, zostaje 4 punkty many.

Zaatakuj raz — zdrowie wrogów zmienia się na 0, 0, 2, 3, 4, 4, 8, 16, 16. Dwóch wrogów ginie, zostaje 17 punktów many.

Nałóż Więź dusz na wrogów o zdrowiu 4, 16, zostaje 3 punkty many.

Zaatakuj dwa razy — zdrowie wrogów zmienia się na 0, 1, 2, 4, 8, 14, 16. Jeden wróg ginie, zostaje 8 punktów many.

Nałóż Więź dusz na wroga o zdrowiu 8, zostaje 1 punkt many.

Zaatakuj raz — zdrowie wrogów zmienia się na 0, 1, 4, 7, 13, 16. Jeden wróg ginie, zostaje 7 punktów many.

Zaatakuj raz — zdrowie wrogów zmienia się na 0, 4, 6, 12, 16. Jeden wróg ginie, zostaje 13 punktów many.

Nałóż Więź dusz na wroga o zdrowiu 4, zostaje 6 punktów many.

Zaatakuj cztery razy — zdrowie wrogów zmienia się na 0, 2, 8, 16. Jeden wróg ginie, zostaje 9 punktów many.

Nałóż Więź dusz na wroga o zdrowiu 16, zostaje 2 punkty many.

Zaatakuj dwa razy — zdrowie wrogów zmienia się na 0, 6, 14. Jeden wróg ginie, zostaje 7 punktów many.

Zaatakuj sześć razy — zdrowie wrogów zmienia się na 0, 8. Jeden wróg ginie, zostaje 8 punktów many.

Zaatakuj osiem razy — wszyscy wrogowie giną, zostaje 0 punktów many.

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.