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