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.