문제

우유의 날을 맞아 명섭이는 우유를 할인된 가격에 판매하고 있다. 명섭이는 $1$번부터 $N$번까지 총 $N$가지의 판매 방식을 제안한다. $i$번째 판매 방식은 $2^{i-1}$개의 우유가 들어있는 우유 한 통을 $a_i$원에 판매하는 것이다. 각 판매 방식은 원하는 만큼 여러 번 이용할 수 있다.

민재는 $Q$개의 독립적인 질문을 하려고 한다. 각 질문에서 민재는 우유를 적어도 $x$개 구매하기 위해 필요한 최소 비용이 얼마인지 알고 싶어 한다.

입력

첫째 줄에 판매 방식의 수 $N$과 질문의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N \le 10^5$; $1 \le Q \le 10^4$)

둘째 줄에 각 판매 방식의 가격 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 10^9$; $a_i < a_{i+1}$)

이어서 $Q$개의 줄에 걸쳐 각 질문에 해당하는 정수 $x$가 한 줄에 하나씩 주어진다. ($1 \le x \le 10^9$)

출력

각 질문에 대해 우유를 적어도 $x$개 구매하는 데 필요한 최소 비용을 한 줄에 하나씩 출력한다.

이 문제에서 다루는 정수의 값이 매우 클 수 있으므로, C/C++의 long long과 같은 64비트 정수 자료형을 사용해야 할 수도 있음에 유의하라.

예제 입력 1

2 4
10 15
1
2
6
7

예제 출력 1

10
15
45
55

예제 입력 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

점수

• 3-4번 데이터: $N \le 2$
• 5-8번 데이터: $N \le 10$
• 9-16번 데이터: 추가적인 제약 조건이 없다.