题目背景

翻译自 NOI SG 2024 Prelim E.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|$ 元。如果车上没有炸药，则你不需要支付任何费用。

请求出在花费最小的情况下的操作序列。

输入格式

第一行，两个整数 $n,c$；

第二行，一行 $n$ 个整数，表示 $a$。

第三行，一行 $n$ 个整数，表示 $b$。

输出格式

第一行，一个整数表示最小花费。

第二行，输出 $2n$ 个整数，表示你访问的工厂和矿井坐标，按照访问顺序输出。

例如你执行了四次操作：pickup(3)，offload(5)，pickup(6)，offload(2)，则你应该输出 3 5 6 2。

3 2
12 14 4
9 5 8

7
4 5 14 12 9 8

提示

【样例 #1 解释】

按照顺序访问工厂 $3$，矿井 $2$，工厂 $2$，工厂 $1$，矿井 $1$，矿井 $3$，即可得到最小值 $7$。

以此样例为例，如果你只输出正确的最小代价 $7$，你将可以得到该测试点 $50\%$ 的分数。

【数据范围】

对于 $100\%$ 的数据，$1 \le n,c \le 1000,1 \le a_i,b_i \le 10000$。