P16734 [GKS 2019 #D] Food Stalls

每个人都喜欢街头小吃，尤其是 Bitetown 的当地居民！因此，你决定在 Bitetown 的主干道上建造恰好 $K$ 个食品摊位和一个仓库。 主干道是一条长度为 $10^9$ 米的水平直线。有 $N$ 个**地点**允许你建造摊位或仓库。你不能在街道上的其他地方建造。第 $i$ 个地点距离街道左端 $X_i$ 米。 你可以在第 $i$ 个地点最多建造一个摊位或仓库（但不能两者都建），建造费用为 $C_i$ 美元。此外，如果仓库建在第 $j$ 个地点，那么在第 $i$ 个地点建造一个摊位的额外费用为 $|X_j - X_i|$ 美元。 请找出建造恰好 $K$ 个食品摊位和一个仓库的最小总费用。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $K$ 和 $N$，分别表示你必须建造的摊位数量和街道上的地点数量。 第二行包含 $N$ 个整数 $X_i$，其中第 $i$ 个整数表示第 $i$ 个地点距离街道左端的距离（米）。 第三行包含 $N$ 个整数 $C_i$，其中第 $i$ 个整数表示在第 $i$ 个地点建造一个摊位或仓库的费用。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是建造 $K$ 个摊位的最小总费用。

在样例 1 中，你必须建造 $K = 2$ 个摊位和一个仓库，共有 $N = 4$ 个可建地点。一种可行方案是在第 3 个地点建仓库，费用为 $80$ 美元；在第 2 个和第 4 个地点建摊位。 - 在第 2 个地点建摊位的费用为 $70 + |3 - 2| = 71$ 美元。 - 在第 4 个地点建摊位的费用为 $20 + |3 - 10| = 27$ 美元。 总费用为 $178$ 美元，这是可能的最小值，因此答案为 $178$。 在样例 2 中，你必须建造 $K = 1$ 个摊位和一个仓库，共有 $N = 5$ 个可建地点。一种可行方案是在第 2 个地点建仓库，费用为 $35$ 美元；在第 3 个地点建摊位，费用为 $26 + |301 - 300| = 27$ 美元。总费用为 $62$ 美元，是最小值。 在样例 3 中，你必须建造 $K = 6$ 个摊位和一个仓库，共有 $N = 7$ 个可建地点。一种可行方案是在第 4 个地点建仓库，并在其余 $6$ 个地点建摊位。留给参赛者验证其总费用为 $82$ 美元，且为最小值。注意，本例中地点的距离并非按升序排列。 ### 限制条件 $1 \le T \le 100$。 $1 \le K < N$。 对于所有 $i$，$1 \le C_i \le 10^9$。 对于所有 $i$，$1 \le X_i \le 10^9$。 对于所有 $i \neq j$，$X_i \neq X_j$。 **测试集 1（可见）** $2 \le N \le 100$。 **测试集 2（隐藏）** 最多有 $5$ 个测试用例满足 $500 < N \le 10^5$。 其余测试用例满足 $2 \le N \le 500$。 翻译由 DeepSeek V4 Pro 完成