Mô tả bài toán
Bạn đang chơi một trò chơi phiêu lưu. Là một pháp sư, bạn cần sử dụng phép thuật để đối phó với một số kẻ địch trước mặt. Mỗi kẻ địch có một cấp độ là một số nguyên từ $1$ đến $n$. Kẻ địch cấp $i$ có $2^{i-1}$ điểm máu.
Bạn có thể sử dụng hai loại phép thuật:
- Liên kết linh hồn (Soul Link): tiêu tốn $m$ điểm năng lượng, gắn hiệu ứng "Liên kết linh hồn" lên một kẻ địch. Hiệu ứng này kéo dài cho đến khi kẻ địch đó chết.
- Tấn công (Attack): tiêu tốn $1$ điểm năng lượng, gây $1$ điểm sát thương lên tất cả kẻ địch đang có hiệu ứng "Liên kết linh hồn", tức là làm giảm máu của chúng đi $1$. Khi máu của một kẻ địch giảm xuống $0$, kẻ địch đó sẽ chết và bạn nhận được $m$ điểm năng lượng làm phần thưởng.
Trong số các kẻ địch trước mặt bạn, có $a_i$ kẻ địch cấp $i$. Bạn có thể sử dụng hai phép thuật này bao nhiêu lần tùy ý, nhưng tại mọi thời điểm điểm năng lượng của bạn không được nhỏ hơn $0$. Để đánh bại tất cả kẻ địch, bạn cần tối thiểu bao nhiêu điểm năng lượng ban đầu?
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 500$), biểu thị số lượng bộ dữ liệu.
Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), lần lượt biểu thị cấp độ tối đa của kẻ địch và lượng năng lượng cần thiết để thi triển Liên kết linh hồn.
Dòng thứ hai chứa $n$ số nguyên dương. Số nguyên thứ $i$ là $a_i$ biểu thị số lượng kẻ địch cấp $i$.
Đối với mỗi bộ dữ liệu, đảm bảo rằng $0 \le a_i \le 10^9$ và $\sum_{i=1}^n a_i > 0$.
Kết quả
Đối với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên, biểu thị lượng năng lượng ban đầu tối thiểu cần thiết để đánh bại tất cả kẻ địch.
Ví dụ
Dữ liệu vào 1
2 5 7 5 2 4 1 2 6 4 1 1 4 5 1 4
Kết quả 1
34 48
Ghi chú
Giải thích cho bộ dữ liệu đầu tiên:
Ban đầu, có 14 kẻ địch với lượng máu lần lượt là 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.
Ban đầu có 34 năng lượng, trước tiên gắn Liên kết linh hồn lên các kẻ địch có máu 1, 1, 1, 1, còn lại 6 năng lượng.
Tấn công một lần, máu của kẻ địch trở thành 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Bốn kẻ địch chết, còn lại 33 năng lượng.
Gắn Liên kết linh hồn lên các kẻ địch có máu 1, 2, 2, 4, còn lại 5 năng lượng.
Tấn công một lần, máu của kẻ địch trở thành 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Một kẻ địch chết, còn lại 11 năng lượng.
Gắn Liên kết linh hồn lên kẻ địch có máu 4, còn lại 4 năng lượng.
Tấn công một lần, máu của kẻ địch trở thành 0, 0, 2, 3, 4, 4, 8, 16, 16. Hai kẻ địch chết, còn lại 17 năng lượng.
Gắn Liên kết linh hồn lên các kẻ địch có máu 4, 16, còn lại 3 năng lượng.
Tấn công hai lần, máu của kẻ địch trở thành 0, 1, 2, 4, 8, 14, 16. Một kẻ địch chết, còn lại 8 năng lượng.
Gắn Liên kết linh hồn lên kẻ địch có máu 8, còn lại 1 năng lượng.
Tấn công một lần, máu của kẻ địch trở thành 0, 1, 4, 7, 13, 16. Một kẻ địch chết, còn lại 7 năng lượng.
Tấn công một lần, máu của kẻ địch trở thành 0, 4, 6, 12, 16. Một kẻ địch chết, còn lại 13 năng lượng.
Gắn Liên kết linh hồn lên kẻ địch có máu 4, còn lại 6 năng lượng.
Tấn công bốn lần, máu của kẻ địch trở thành 0, 2, 8, 16. Một kẻ địch chết, còn lại 9 năng lượng.
Gắn Liên kết linh hồn lên kẻ địch có máu 16, còn lại 2 năng lượng.
Tấn công hai lần, máu của kẻ địch trở thành 0, 6, 14. Một kẻ địch chết, còn lại 7 năng lượng.
Tấn công sáu lần, máu của kẻ địch trở thành 0, 8. Một kẻ địch chết, còn lại 8 năng lượng.
Tấn công tám lần, tất cả kẻ địch chết, còn lại 0 năng lượng.