시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB42201856.250%

문제

On National Milk Day, Farmer John is offering exclusive prices on buckets of milk! He has $N$ ($1 \leq N \leq 10^5$) deals numbered from $1$ to $N$. For the $i$'th deal, he is offering $2^{i-1}$ buckets of milk for $a_i$ ($1 \leq a_i \leq 10^9, a_i < a_{i+1}$) moonies. The same deal may be taken any non-negative integer number of times.

You are thinking about $Q$ ($1 \leq Q \leq 10^4$) independent queries. For each query, you have an integer $x$ ($1 \leq x \leq 10^9$) in mind and wonder what is the minimum cost to purchase at least $x$ buckets of milk.

입력

The first line contains two integers $N$ and $Q$.

The following line contains $a_1, a_2, \ldots, a_N$.

Each of the following $Q$ lines contains an integer $x$, representing a query.

출력

For each query, output the minimum cost on a new line.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

예제 입력 1

2 4
10 15
1
2
6
7

예제 출력 1

10
15
45
55

In the example above, Farmer John is offering 2 deals: 1 bucket of milk for 10 moonies and 2 buckets of milk for 15 moonies.

The cheapest cost to buy 1 bucket is just the cost of the 1 bucket deal and the cheapest cost to buy 2 buckets is just the cost of the 2 bucket deal.

To get 6 buckets, the cheapest way is to purchase 3 of the 2 bucket deal for a total of 45 moonies.

To get 7 buckets, the cheapest way is to purchase 3 of the 2 bucket deal and 1 of the 1 bucket deal for a total of 55 moonies.

예제 입력 2

4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
101

예제 출력 2

10
20
30
30
40
50
60
60
120
760

In this example, Farmer John is offering a total of 4 deals for 1, 2, 4, and 8 buckets. For each of the 10 queries, the corresponding output indicates the minimum cost to purchase at least that amount of milk. Sometimes, it is cheaper to purchase more than the specified amount.