Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓
統計

Сипаттамасы

Сіз шытырман оқиғалы ойын ойнап жатырсыз. Сиқыршы ретінде алдыңыздағы бірнеше жаумен күресу үшін сиқыр қолдануыңыз керек. Әр жаудың $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 мана қалады.

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.