U235751 【模板】k 叉哈夫曼树

给定 $n$ 个权值作为 $n$ 个叶子结点，构造一棵 $k$ 叉树，若该树的带权路径长度达到最小，称为哈夫曼树。 现在，给定 $n$ 个叶子结点的权值 $w_i$ ，请你构造哈夫曼树，并输出该树的带权路径长度。 即求 $ ans = \sum_{\mathclap{}} w_{i} \times l_i $ 。

第一行包含整数 $n$ 和 $k$ ，表示叶子结点数量和树的分支数。 接下来第 $2$ 行到第 $n+1$ 行每行 1 个整数 $w_i$ ，表示每个叶子结点的权值。

输出一个整数 $ans$ ，表示生成哈夫曼树的带权路径长度。

对于 $100\%$ 的数据 $ 1\leq n \leq 10^5 $ ， $ 2\leq k \leq 9 $ 。