Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 256 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Deskripsi

Anda sedang memainkan sebuah permainan petualangan. Sebagai seorang penyihir, Anda perlu menggunakan sihir untuk menghadapi beberapa musuh di hadapan Anda. Setiap musuh memiliki level yang merupakan bilangan bulat antara $1$ hingga $n$. Musuh berlevel $i$ memiliki $2^{i-1}$ poin nyawa.

Anda dapat menggunakan dua jenis mantra:

  • Soul Link: menghabiskan $m$ mana dan memberikan efek "Soul Link" kepada satu musuh. Efek ini bertahan hingga musuh tersebut mati.
  • Attack: menghabiskan $1$ mana dan memberikan $1$ kerusakan kepada semua musuh yang memiliki efek "Soul Link", yaitu mengurangi nyawa mereka sebesar $1$. Begitu nyawa suatu musuh turun menjadi $0$, musuh tersebut mati, dan Anda memperoleh $m$ mana sebagai hadiah.

Di antara musuh-musuh di hadapan Anda, terdapat $a_i$ musuh berlevel $i$. Anda boleh menggunakan kedua mantra tersebut berapa kali pun, tetapi pada saat kapan pun mana Anda tidak boleh kurang dari $0$. Berapakah mana awal minimum yang Anda perlukan untuk mengalahkan semua musuh?

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 500$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), yang masing-masing menyatakan level musuh maksimum dan biaya mana untuk Soul Link.

Baris kedua berisi $n$ bilangan bulat positif. Bilangan bulat ke-$i$, yaitu $a_i$, menyatakan banyaknya musuh berlevel $i$.

Untuk setiap kasus uji, dijamin bahwa $0 \le a_i \le 10^9$ dan $\sum_{i=1}^n a_i > 0$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat, yang menyatakan mana awal minimum yang diperlukan untuk mengalahkan semua musuh.

Contoh

Masukan 1

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

Keluaran 1

34
48

Catatan

Penjelasan untuk kasus uji pertama:

Pada awalnya, terdapat 14 musuh dengan nilai nyawa 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.

Dengan 34 mana di awal, pertama-tama berikan Soul Link pada musuh dengan nyawa 1, 1, 1, 1, menyisakan 6 mana.

Serang sekali, dan nyawa musuh menjadi 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Empat musuh mati, menyisakan 33 mana.

Berikan Soul Link pada musuh dengan nyawa 1, 2, 2, 4, menyisakan 5 mana.

Serang sekali, dan nyawa musuh menjadi 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Satu musuh mati, menyisakan 11 mana.

Berikan Soul Link pada musuh dengan nyawa 4, menyisakan 4 mana.

Serang sekali, dan nyawa musuh menjadi 0, 0, 2, 3, 4, 4, 8, 16, 16. Dua musuh mati, menyisakan 17 mana.

Berikan Soul Link pada musuh dengan nyawa 4, 16, menyisakan 3 mana.

Serang dua kali, dan nyawa musuh menjadi 0, 1, 2, 4, 8, 14, 16. Satu musuh mati, menyisakan 8 mana.

Berikan Soul Link pada musuh dengan nyawa 8, menyisakan 1 mana.

Serang sekali, dan nyawa musuh menjadi 0, 1, 4, 7, 13, 16. Satu musuh mati, menyisakan 7 mana.

Serang sekali, dan nyawa musuh menjadi 0, 4, 6, 12, 16. Satu musuh mati, menyisakan 13 mana.

Berikan Soul Link pada musuh dengan nyawa 4, menyisakan 6 mana.

Serang empat kali, dan nyawa musuh menjadi 0, 2, 8, 16. Satu musuh mati, menyisakan 9 mana.

Berikan Soul Link pada musuh dengan nyawa 16, menyisakan 2 mana.

Serang dua kali, dan nyawa musuh menjadi 0, 6, 14. Satu musuh mati, menyisakan 7 mana.

Serang enam kali, dan nyawa musuh menjadi 0, 8. Satu musuh mati, menyisakan 8 mana.

Serang delapan kali, dan semua musuh mati, menyisakan 0 mana.

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.