Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 256 MB Points totaux : 100 Hackable ✓
Statistiques

問題文

あなたは冒険ゲームをプレイしています。魔法使いであるあなたは、目の前にいる何体かの敵に魔法で対処しなければなりません。各敵にはレベルがあり、レベルは $1$ から $n$ までの整数です。レベル $i$ の敵は $2^{i-1}$ の体力を持っています。

あなたは 2 種類の呪文を使うことができます:

  • ソウルリンク (Soul Link):マナを $m$ 消費し、1 体の敵に「ソウルリンク」効果を付与します。この効果はその敵が死亡するまで持続します。
  • 攻撃 (Attack):マナを $1$ 消費し、「ソウルリンク」効果がついているすべての敵に $1$ ダメージを与えます(つまり体力を $1$ 減らします)。敵の体力が $0$ になるとその敵は死亡し、報酬としてマナを $m$ 獲得します。

目の前にいる敵のうち、レベル $i$ の敵は $a_i$ 体います。2 種類の呪文は何回でも使えますが、どの時点でもマナが $0$ 未満になってはいけません。すべての敵を倒すために必要な最小の初期マナはいくつですか?

入力

1 行目にはテストケースの数を表す整数 $T$ ($1 \le T \le 500$) が与えられます。

各テストケースについて、1 行目には敵の最大レベルとソウルリンクの消費マナを表す 2 つの整数 $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$) が与えられます。

2 行目には $n$ 個の正の整数が与えられます。$i$ 番目の整数 $a_i$ はレベル $i$ の敵の数を表します。

各テストケースについて、$0 \le a_i \le 10^9$ および $\sum_{i=1}^n a_i > 0$ が保証されます。

出力

各テストケースについて、すべての敵を倒すために必要な最小の初期マナを表す整数を 1 行に出力してください。

入出力例

入力例 1

2
5 7
5 2 4 1 2
6 4
1 1 4 5 1 4

出力例 1

34
48

注記

1 番目のテストケースの説明:

最初、14 体の敵がいて、それぞれの体力は 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16 です。

初期マナ 34 で、まず体力 1, 1, 1, 1 の敵にソウルリンクを付与し、残りマナは 6 になります。

1 回攻撃すると、敵の体力は 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16 になります。4 体の敵が死亡し、残りマナは 33 になります。

体力 1, 2, 2, 4 の敵にソウルリンクを付与し、残りマナは 5 になります。

1 回攻撃すると、敵の体力は 0, 1, 1, 3, 4, 4, 4, 8, 16, 16 になります。1 体の敵が死亡し、残りマナは 11 になります。

体力 4 の敵にソウルリンクを付与し、残りマナは 4 になります。

1 回攻撃すると、敵の体力は 0, 0, 2, 3, 4, 4, 8, 16, 16 になります。2 体の敵が死亡し、残りマナは 17 になります。

体力 4, 16 の敵にソウルリンクを付与し、残りマナは 3 になります。

2 回攻撃すると、敵の体力は 0, 1, 2, 4, 8, 14, 16 になります。1 体の敵が死亡し、残りマナは 8 になります。

体力 8 の敵にソウルリンクを付与し、残りマナは 1 になります。

1 回攻撃すると、敵の体力は 0, 1, 4, 7, 13, 16 になります。1 体の敵が死亡し、残りマナは 7 になります。

1 回攻撃すると、敵の体力は 0, 4, 6, 12, 16 になります。1 体の敵が死亡し、残りマナは 13 になります。

体力 4 の敵にソウルリンクを付与し、残りマナは 6 になります。

4 回攻撃すると、敵の体力は 0, 2, 8, 16 になります。1 体の敵が死亡し、残りマナは 9 になります。

体力 16 の敵にソウルリンクを付与し、残りマナは 2 になります。

2 回攻撃すると、敵の体力は 0, 6, 14 になります。1 体の敵が死亡し、残りマナは 7 になります。

6 回攻撃すると、敵の体力は 0, 8 になります。1 体の敵が死亡し、残りマナは 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.