Coat Rack

Time limit1sMemory limit1024 MB

Summary

Sort garments and targets; sliding garments keeps their order and may stack them, so assign each target to a position minimizing total distance under order constraints.

Level: Hard8 of 10
Topics: Dynamic programming, Divide and conquer, Sorting, Greedy
Solved: No attempts yet

Problem

Zigmas works in a cloakroom where fussy people hang up their own clothes but then end up unhappy with the exact spot where they hung them.

The cloakroom has a single straight coat rack on which $N$ people have each hung one garment. Every garment hangs at a point with integer coordinate $a_i$ , and at most one garment hangs at any single coordinate. The owner of each garment wants to move it to the point with coordinate $b_i$ , and that owner's dissatisfaction equals the distance from the garment's current position to the desired position.

Zigmas wants to make the total dissatisfaction as small as possible by sliding the garments along the rack. He may not take any garment off the rack, so the garments cannot change their relative order, but he may push several garments so close together that they share the same coordinate.

Compute the minimum possible total dissatisfaction after the garments have been rearranged.

Input

The first line contains two space-separated integers: the number of garments $N$ and the length of the rack $L$ .

The second line contains $N$ space-separated integers $a_i$ , the initial coordinates of the garments.

The third line contains $N$ space-separated integers $b_i$ , the coordinates where the owners want their garments to end up.

Output

Print, on a single line, the minimum possible total dissatisfaction after the garments have been rearranged.

Constraints

$2 \le N \le 100\,000$
$0 \le a_i, b_i \le L \le 10^9$
$N \le L + 1$
$a_i \ne a_j$ when $i \ne j$

Examples1

Example 1
Input
```
4 6
5 1 2 4
4 5 3 2
```
Expected output
```
3
```