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$ من المانا كمكافأة.

من بين الأعداء الذين أمامك، يوجد $a_i$ من الأعداء من المستوى $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.