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

備註

第一個測試數據嘅解釋:

起初,有 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.