Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 256 MB Points totaux : 100 Hackable ✓
Statistiques

Описание

Вы играете в приключенческую игру. Будучи магом, вам нужно использовать магию, чтобы справиться с несколькими врагами перед вами. У каждого врага есть уровень — целое число от $1$ до $n$. Враг уровня $i$ имеет $2^{i-1}$ единиц здоровья.

Вы можете использовать два вида заклинаний:

  • Связь душ (Soul Link): расходует $m$ единиц маны и накладывает эффект «Связь душ» на одного врага. Этот эффект длится до тех пор, пока этот враг не умрёт.
  • Атака (Attack): расходует $1$ единицу маны и наносит $1$ единицу урона всем врагам с эффектом «Связь душ», то есть уменьшает их здоровье на $1$. Как только здоровье какого-либо врага падает до $0$, этот враг умирает, а вы получаете $m$ единиц маны в качестве награды.

Среди стоящих перед вами врагов есть $a_i$ врагов уровня $i$. Вы можете использовать оба заклинания любое количество раз, но ни в какой момент времени ваша мана не может стать меньше $0$. Какое минимальное начальное количество маны вам нужно, чтобы победить всех врагов?

Входные данные

Первая строка содержит одно целое число $T$ ($1 \le T \le 500$), обозначающее количество наборов входных данных.

Для каждого набора входных данных первая строка содержит два целых числа $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), обозначающих максимальный уровень врагов и стоимость заклинания «Связь душ» в мане соответственно.

Вторая строка содержит $n$ положительных целых чисел. $i$-е целое число $a_i$ обозначает количество врагов уровня $i$.

Для каждого набора входных данных гарантируется, что $0 \le a_i \le 10^9$ и $\sum_{i=1}^n a_i > 0$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую одно целое число — минимальное начальное количество маны, необходимое для победы над всеми врагами.

Примеры

Входные данные 1

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

Выходные данные 1

34
48

Примечание

Пояснение к первому набору входных данных:

Изначально есть 14 врагов со значениями здоровья 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.

Имея вначале 34 маны, сначала наложим «Связь душ» на врагов со здоровьем 1, 1, 1, 1, останется 6 маны.

Атакуем один раз: здоровье врагов станет 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Четыре врага умирают, остаётся 33 маны.

Наложим «Связь душ» на врагов со здоровьем 1, 2, 2, 4, останется 5 маны.

Атакуем один раз: здоровье врагов станет 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Один враг умирает, остаётся 11 маны.

Наложим «Связь душ» на врага со здоровьем 4, останется 4 маны.

Атакуем один раз: здоровье врагов станет 0, 0, 2, 3, 4, 4, 8, 16, 16. Два врага умирают, остаётся 17 маны.

Наложим «Связь душ» на врагов со здоровьем 4, 16, останется 3 маны.

Атакуем два раза: здоровье врагов станет 0, 1, 2, 4, 8, 14, 16. Один враг умирает, остаётся 8 маны.

Наложим «Связь душ» на врага со здоровьем 8, останется 1 мана.

Атакуем один раз: здоровье врагов станет 0, 1, 4, 7, 13, 16. Один враг умирает, остаётся 7 маны.

Атакуем один раз: здоровье врагов станет 0, 4, 6, 12, 16. Один враг умирает, остаётся 13 маны.

Наложим «Связь душ» на врага со здоровьем 4, останется 6 маны.

Атакуем четыре раза: здоровье врагов станет 0, 2, 8, 16. Один враг умирает, остаётся 9 маны.

Наложим «Связь душ» на врага со здоровьем 16, останется 2 маны.

Атакуем два раза: здоровье врагов станет 0, 6, 14. Один враг умирает, остаётся 7 маны.

Атакуем шесть раз: здоровье врагов станет 0, 8. Один враг умирает, остаётся 8 маны.

Атакуем восемь раз: все враги умирают, остаётся 0 маны.

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.