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}$의 체력을 가집니다.

당신은 두 가지 주문을 사용할 수 있습니다:

  • 소울 링크 (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.