Background

Translated from NOI SG 2024 Prelim E.Explosives。

Problem Description

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.

Input Format

The first line contains two integers $n,c$。

The second line contains $n$ integers, representing $a$。

The third line contains $n$ integers, representing $b$。

Output Format

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。

3 2
12 14 4
9 5 8

7
4 5 14 12 9 8

Hint

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

For $100\%$ of the data, $1 \le n,c \le 1000,1 \le a_i,b_i \le 10000$。

Translated by ChatGPT 5