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