问题陈述
21XX年,一年一度的编程大赛》Japan Algorithmist GrandPrix (JAG)“一直是最受欢迎的智力运动项目之一。 作为JAG的主席,您正在准备今年的JAG比赛。
JAG 采用淘汰赛形式进行。 今年,$N$ 选手将参加 JAG 比赛。 锦标赛被表示为具有 $N$ 叶节点的二叉树,参赛者被一对一地分配到其中。 每场比赛都有两名选手进行比赛。胜者进入下一轮,败者被淘汰出局。 唯一比其他参赛者幸存的参赛者就是冠军。 最终的匹配对应于二叉树的根节点。
你知道每个参赛者的实力,$A_1, A_2, \cdots, A_N$,用整数表示。 当两个参赛者较量时,总是实力更强的一方获胜。 如果他们的实力相同,则随机确定获胜者。
过去的JAG,有观众抱怨单方面的比赛太无聊。 为了让JAG更具吸引力,您需要找到良好的锦标赛配置。
让我们定义一下比赛和锦标赛的无聊程度。 对于第$i$个选手和第$j$个选手进行比赛的比赛,我们将比赛的无聊度定义为两名选手的实力差异$|A_i - A_j|$。 锦标赛的无聊度被定义为锦标赛中所有比赛的无聊度之和。
你的目的是尽量减少锦标赛的无聊感。
您可以考虑任何形式的锦标赛,包括不平衡的锦标赛,但前提是锦标赛的高度必须小于或等于 $K$。 锦标赛的高度定义为从二叉树的根节点到任意叶节点的简单路径上的最大匹配数。
图 K-1 显示了示例输入 1 的两种可能的锦标赛。 左边的高度是$2$,右边的高度是$3$。
图 K-1。样本输入 1 的两个可能的锦标赛
编写一个程序来计算锦标赛的最低无聊度。
输入
输入由具有以下格式的单个测试用例组成。
$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$
输入的第一行包含两个整数 $N$ ($2 \le N \le 1{,}000$) 和 $K$ ($1 \le K \le 50$)。您可以假设 $N \le 2^K$。 第二行包含$N$个整数$A_1、A_2、\cdots A_N$。 $A_i$ ($1 \le A_i \le 100{,}000$) 代表第 $i$ 位参赛者的实力。
输出
输出最佳锦标赛配置所达到的最小无聊度值。
示例输入 1
4 3 1 3 4 7
样本输入 1 的输出
6
示例输入 2
5 3 1 3 4 7 9
样本输入 2 的输出
10
示例输入 3
18 7 67 64 52 18 39 92 84 66 19 64 1 66 35 34 45 2 79 34
样本输入 3 的输出
114