[NOISG 2024 Prelim] Explosives

你是一名运送炸弹的卡车司机。 有 $n$ 座工厂（生产炸弹）和 $n$ 座矿井（需要炸弹）排列在一条直线上。第 $i$ 座工厂的坐标为 $a_i$，第 $j$ 座矿井的坐标为 $b_j$。并且，所有 $a_i$ 和 $b_j$ 都均不相等。 你今天需要在每一座工厂各领取一个炸弹，并将每一个炸弹送到某一个矿井中。初始时，你的坐标为 $0$。为了完成此任务，你可以进行以下两种操作： - `pickup(x)`：从你当前的位置驾驶卡车到坐落在 $x$ 的工厂。执行这次操作需要同时满足以下两个条件： - 有一个 $i$，满足 $x=a_i$。 - 你的卡车最多装了 $c-1$ 个炸弹。 - `offload(x)`：从你当前的位置驾驶卡车到坐落在 $x$ 的矿井。执行这次操作需要同时满足以下两个条件： - 有一个 $j$，满足 $x=b_j$。 - 你的卡车最少装了 $1$ 个炸弹。 由于炸弹十分危险，所以在你的卡车上需要一名安全员。如果你从点 $x$ 到点 $y$，且车上装有炸弹，那么你需要付给安全员 $|x-y|$ 元。如果车上没有炸药，则你不需要支付任何费用。 请求出在花费最小的情况下的操作序列。 ## Input 第一行，两个整数 $n,c$； 第二行，一行 $n$ 个整数，表示 $a$。 第三行，一行 $n$ 个整数，表示 $b$。 ## Output 第一行，一个整数表示最小花费。 第二行，输出 $2n$ 个整数，表示你访问的工厂和矿井坐标，按照访问顺序输出。 例如你执行了四次操作：`pickup(3)`，`offload(5)`，`pickup(6)`，`offload(2)`，则你应该输出 `3 5 6 2`。 [samples] ## Background 翻译自 [NOI SG 2024 Prelim E.Explosives](https://github.com/noisg/noi-2024-prelim)。 ## Note ### 【样例 #1 解释】 按照顺序访问工厂 $3$，矿井 $2$，工厂 $2$，工厂 $1$，矿井 $1$，矿井 $3$，即可得到最小值 $7$。 以此样例为例，如果你只输出正确的最小代价 $7$，你将可以得到该测试点 $50\%$ 的分数。 ### 【数据范围】 |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$0$|$0$|样例| |$1$|$16$|$c=1$| |$2$|$22$|$a_i\le 5000,b_i>5000$| |$3$|$62$|无| 对于 $100\%$ 的数据，$1 \le n,c \le 1000,1 \le a_i,b_i \le 10000$。