313. Circular Railway
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard
There are
L stations along a circular railway, numbered 1 through
L. Trains travel in both directions, and take 1 minute to get from a station to the neighbouring one (i.e., between 1st and 2nd, between 2nd and 3rd,..., between (
L-1)-th and
L-th and between
L-th and 1-st).
There are
n employee's houses along the railway, and
n offices, each house or office located near a railway station. You are to establish a one-to-one correspondence between houses and offices in such a way that total travel time (sum of travel times of each employee) is minimized.
Input
The first line of the input file contains two integer numbers,
n and
L (1 ≤
n ≤ 50000, 2 ≤
L ≤ 10
9). The second line contains
n locations of the employee's houses, and the third line contains
n locations of the offices. Each location is an integer number between 1 and
L. Some houses or offices or both can be located at the same railway station.
Output
Output the minimal total travel time followed by the description of the one-to-one correspondence. The description should be represented by
n numbers (one for each employee, ordered as in the input), denoting the 1-based index of the office assigned to the corresponding employee.
Example(s)
sample input | sample output |
3 15
1 2 10
11 12 13
|
9
2 3 1
|
sample input | sample output |
4 12
2 5 8 11
6 9 12 3
|
4
4 1 2 3
|