先考虑得到一个多项式复杂度做法：你从上到下逐层剥点，那你的状态是深度不超过 $i$，有 $j$ 个叶子，形成 $k$ 个满二叉树的最小代价，你显然优先剥权值大的点。

不妨对 $a$ 升序排序，做前缀和得到 $S$。

转移是

$$ f_{i,j,k}=\min_{0\leq x}\{f_{i-1,j-x,2k-x}\}+S_j $$

你直接暴力实现是 $\mathcal{O}(dn^3)$ 的，但是我们熟知哈夫曼树深度是 $\mathcal{O}(\log S_n)$ 的，而超过哈夫曼树深度的 $d$ 无意义，所以现在是 $\mathcal{O}(n^3\log S_n)$。

先考虑优化转移复杂度，对下标做一个线性变换，把 $(j,k)$ 变成 $(j,j-k)$，这样发现 $(i,x,y)$ 是从 $(i-1,x-z,2y-x)$ 转移过来，做一个前缀 $\min$ 优化就可以变成 $\mathcal{O}(dn^2)$。

然后我们需要再减少状态数，发现具体来说 $(i,x,y)$ 是从所有满足 $z\leq x$ 的 $(i-1,z,2y-x)$ 转移过来，你感受一下其实 $z\leq x$ 这个限制没那么有用，看起来这个叶子数就会自然满足单调性，你感受一下就可以发现你把这个限制删去求出的答案也一致，因此就可以删去这一维。

于是你的转移变成了

$$ f_{i,j}=\min_{0\leq k}\{f_{i-1,2j-k}+S_k\} $$

显然 $S$ 是凸的，因此 $f_i$ 可以归纳证明是凸的，闵和即可，时间复杂度 $\mathcal{O}(n\log S_n+m)$。