Purchasing Milk

Bác John bán $N$ gói sữa. Gói thứ $i$ cung cấp $2^{i-1}$ xô sữa với giá $a_i$ đồng. Mỗi gói có thể mua nhiều lần.

Cho $Q$ truy vấn, mỗi truy vấn cho một số nguyên $x$, hãy tìm chi phí tối thiểu để mua ít nhất $x$ xô sữa.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ ($1\le N\le {10}^5$) và $Q$ ($1\le Q\le {10}^4$).
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$ ($1\le a_i\le {10}^9$, $a_i<a_{i+1}$).
• $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $x$ ($1\le x\le {10}^9$).

Dữ liệu ra

Với mỗi truy vấn, in ra chi phí tối thiểu trên một dòng.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le Q\le {10}^4$
• $1\le a_i\le {10}^9$, $a_i<a_{i+1}$
• $1\le x\le {10}^9$
• Đáp số có thể lên tới ${10}^{18}$, cần dùng kiểu số nguyên 64-bit.

Ví dụ