Сипаттамасы
Сіз шытырман оқиғалы ойын ойнап жатырсыз. Сиқыршы ретінде алдыңыздағы бірнеше жаумен күресу үшін сиқыр қолдануыңыз керек. Әр жаудың $1$ мен $n$ аралығындағы бүтін сан болатын деңгейі бар. Деңгейі $i$ болатын жаудың $2^{i-1}$ денсаулық ұпайы бар.
Сіз сиқырдың екі түрін қолдана аласыз:
- Жан байланысы (Soul Link): $m$ мана жұмсап, бір жауға «Жан байланысы» әсерін береді. Бұл әсер сол жау өлгенге дейін сақталады.
- Шабуыл (Attack): $1$ мана жұмсап, «Жан байланысы» әсері бар барлық жауға $1$ зақым келтіреді, яғни олардың денсаулығын $1$-ге азайтады. Қандай да бір жаудың денсаулығы $0$-ге түскен бойда, ол жау өледі және сіз сыйақы ретінде $m$ мана аласыз.
Алдыңыздағы жаулардың ішінде деңгейі $i$ болатын $a_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
Ескертпе
Бірінші тест жағдайына түсініктеме:
Бастапқыда денсаулық мәндері 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16 болатын 14 жау бар.
Бастапқыда 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 мана қалады.