คำอธิบายโจทย์
คุณกำลังเล่นเกมผจญภัย ในฐานะนักเวท คุณต้องใช้เวทมนตร์เพื่อจัดการกับศัตรูหลายตัวที่อยู่ตรงหน้า ศัตรูแต่ละตัวมีเลเวลซึ่งเป็นจำนวนเต็มระหว่าง $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 หน่วย