题目描述

每个人都喜欢街头小吃，尤其是 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$ 个摊位的最小总费用。

3
2 4
1 2 3 10
100 70 80 20
1 5
150 300 301 400 700
8 35 26 5 2
6 7
22 21 20 23 26 25 24
10 10 10 10 10 10 10

Case #1: 178
Case #2: 62
Case #3: 82

提示

在样例 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 完成