Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 256 MB Total points: 100 Hackable ✓
Statistics

Опис

Ви граєте в пригодницьку гру. Як маг, ви маєте використовувати магію, щоб упоратися з кількома ворогами перед вами. Кожен ворог має рівень — ціле число від $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.