题目描述

给定 $n$ 个数 $a_1,\dots,a_n$。

定义 $d$-编码树为一棵叶节点个数恰好为 $n$ 的且叶节点深度均不超过 $d$ 的满二叉树 $T$，每个叶节点有权值，$n$ 个权值与 $a$ 中元素一一对应。

定义 $d$-编码树的总权值为 $\sum\limits_{u\in\text{leaf}} dep_u\cdot w_u$，其中 $\text{leaf}$ 为所有叶节点，$dep_u$ 为 $u$ 的深度（根的深度为 $0$），$w_u$ 为 $u$ 的权值。

定义 $d$-哈夫曼树为总权值最小的 $d$-编码树。

给定 $m$ 次询问，每组询问中给定一个 $d$，求 $d$-哈夫曼树的总权值。保证 $2^d\ge n$，即 $d$-哈夫曼树存在。

输入格式

第一行，两个整数 $n,m$。

第二行，$n$ 个整数 $a_1,\dots,a_n$。

接下来 $m$ 行，每行一个整数 $d$，表示一组询问。

输出格式

共 $m$ 行，每行一个整数，依次表示每组询问的答案。

样例

样例输入 1

6 4
1 2 4 7 10 15
3
4
5
6

样例输出 1

92
88
87
87

数据范围

对于 $100\%$ 的数据，$1\le n,m\le 2^{18}$，$1\le a_i\le 10^9$，$1\le d\le n,2^d\ge n$。

$\text{Subtask 1}(10\%):n\le 2^4$。

$\text{Subtask 2}(15\%):n\le 2^7$。

$\text{Subtask 3}(20\%):n\le 2^{10}$。

$\text{Subtask 4}(25\%):m=1$。

$\text{Subtask 5}(30\%):$ 无特殊限制。