Minimum-Cost Number Matching (Hard)

Time limit2sMemory limit128 MB

Summary

Given sorted sets S and T, choose pairs (s,t) with cost |s-t| so every element of both sets appears in at least one pair, minimizing total cost, for sizes up to 500000.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Sorting, Two pointers
Solved: No attempts yet

Problem

You are given two sets S and T of non-negative integers. We want to choose pairs (s, t) with s from S and t from T.

The chosen pairs must satisfy both conditions below.

Any element of S may be paired with any element of T, and any element of T may be paired with any element of S.
Every element of S must appear in at least one chosen pair, and every element of T must also appear in at least one chosen pair.

The cost of a pair (a, b) is |a - b|. The total cost is the sum of the costs of all chosen pairs.

Given S and T, compute the minimum possible total cost.

Input

The first line contains two integers N and M, the number of elements in S and T.

The second line contains the N elements of S in increasing order. The third line contains the M elements of T in increasing order.

Each set has at most 500,000 elements. Every element is an integer between 0 and 1,000,000,000, inclusive.

Output

Print the minimum possible total cost.

Examples1

Example 1
Input
```
5 6
2 8 9 10 11
0 3 4 6 7 11
```
Expected output
```
10
```