곱하기

사슈카는 모든 종류의 수열을 좋아한다. 그녀는 특히 양의 정수 $N$개로 이루어진 자신의 수열 $a_1$, $a_2$, $\dots$, $a_N$을 아주 좋아한다. 방금 곱셈을 배운 여러분을 시험하려고, 사슈카는 이 수열로 문제를 낸다. 그녀는 양의 정수 $N$개로 이루어진 수열 $b_1$, $b_2$, $\dots$, $b_N$을 찾아 $\sum_{i=1}^{N}{a_i \times b_i} = a_1 \times b_1 + a_2 \times b_2 + \cdots + a_N \times b_N$이 최소가 되기를 바란다. 함정이 하나 있다. 수열 $b$에서 같은 값 $x$가 나타나는 자리는 $K$곳을 넘을 수 없다. 즉, $b_i = x$이고 $1 \le i \le N$인 서로 다른 $i$의 개수가 $K$를 넘으면 안 된다. 질문 하나만 답하기엔 너무 싱거우니, 사슈카는 $Q$개의 질문을 한다. $i$번째 질문은 $K = k_i$일 때 합의 최솟값을 묻는다. 사슈카의 질문에 답하는 프로그램 prod를 작성하라.

첫 줄에 수열의 길이 $N$과 질문의 개수 $Q$가 주어진다. 둘째 줄에는 정수 $N$개 $a_1$, $a_2$, $\dots$, $a_N$이 주어진다. 마지막 줄에는 정수 $Q$개 $k_1$, $k_2$, $\dots$, $k_Q$가 주어진다.

한 줄에 정수 $Q$개를 출력한다. $i$번째 수는 $i$번째 질문의 답이다.

• $1 \le N \le 500000$
• $1 \le Q \le 750000$
• $1 \le a_i \le 10^6$
• $1 \le k_i \le 10^9$

첫 번째 질문의 답은 $b = \{1,1,1,2,1,1,1,1\}$로 얻을 수 있다. 이때 $1 \times 40 + 1 \times 100 + 1 \times 77 + 2 \times 15 + 1 \times 44 + 1 \times 22 + 1 \times 47 + 1 \times 38 = 398$이다.