P10712 [NOISG 2024 Prelim] Explosives

Translated from [NOI SG 2024 Prelim E.Explosives](https://github.com/noisg/noi-2024-prelim)。

You are a truck driver transporting bombs. There are $n$ factories (producing bombs) and $n$ mines (needing bombs) arranged on a straight line. The coordinate of the $i$-th factory is $a_i$, and the coordinate of the $j$-th mine is $b_j$. Also, all $a_i$ and $b_j$ are pairwise distinct. Today, you need to pick up one bomb from each factory, and deliver each bomb to some mine. Initially, your position is $0$. To complete this task, you may perform the following two operations: - `pickup(x)`: Drive the truck from your current position to the factory located at $x$. To perform this operation, the following two conditions must both hold: - There exists an $i$ such that $x=a_i$。 - Your truck currently carries at most $c-1$ bombs. - `offload(x)`: Drive the truck from your current position to the mine located at $x$. To perform this operation, the following two conditions must both hold: - There exists a $j$ such that $x=b_j$。 - Your truck currently carries at least $1$ bomb. Because bombs are very dangerous, a safety officer must be on your truck. If you travel from point $x$ to point $y$ while the truck is carrying bombs, then you need to pay the safety officer $|x-y|$ dollars. If the truck is carrying no bombs, then you do not need to pay any cost. Find an operation sequence with the minimum total cost.

The first line contains two integers $n,c$。 The second line contains $n$ integers, representing $a$。 The third line contains $n$ integers, representing $b$。

The first line contains one integer, the minimum cost. The second line outputs $2n$ integers, representing the coordinates of the factories and mines you visit, in the order you visit them. For example, if you perform four operations: `pickup(3)`, `offload(5)`, `pickup(6)`, `offload(2)`, then you should output `3 5 6 2`。

### Sample #1 Explanation Visit factory $3$, mine $2$, factory $2$, factory $1$, mine $1$, mine $3$ in this order, and you can obtain the minimum value $7$。 In this sample, if you only output the correct minimum cost $7$, you can get $50\%$ of the score for this testdata point. ### Constraints |$\text{Subtask}$|Score|Special Property| |:-:|:-:|:-:| |$0$|$0$|Sample| |$1$|$16$|$c=1$| |$2$|$22$|$a_i\le 5000,b_i>5000$| |$3$|$62$|None| For $100\%$ of the data, $1 \le n,c \le 1000,1 \le a_i,b_i \le 10000$。 Translated by ChatGPT 5