In Ringworld, there are ~M~ cities numbered from ~1~ to ~M~ which lie uniformly spaced along a circular, two-way road. It takes one hour to travel between city ~i~ and city ~i+1~ for ~1 \le i \le M~ and one hour to travel between city ~1~ and city ~M~.
There are ~N~ students and ~N~ teachers living in the cities. You would like to assign every teacher to a distinct student such that the sum of the times needed for each student to travel to their assigned teacher's city is minimized.
What is the minimum sum of the travel times for a teacher-student assignment?
The standard input will contain 10 datasets. Each dataset begins with two integers ~N~ and ~M~ ~(1 \le N \le 5 \times 10^5, 1 \le M \le 10^9)~.
The next line contains ~N~ integers ~A_i~ ~(1 \le A_i \le M)~ such that student ~i~ lives in city ~A_i~. The third line contains ~N~ integers ~B_i~ ~(1 \le B_i \le M)~ such that teacher ~i~ lives in city ~B_i~. At most one student or teacher lives in each city.
for the first 4 cases, ~N \le 1000~.
For each dataset, output the minimum sum of the travel times for a teacher-student assignment.
Sample Input (Two Datasets Shown)
2 5 1 4 5 3 5 100 10 20 30 40 50 60 70 80 90 100
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org