385. Valentine's Matchmaking

0

Medium

Today is Valentine's Day in Russia, where the number of girls is greater than the number of boys. Each boy has a certain number of chocolates, and each girl has a certain number of candies. As the evening's anchor, your goal is to pair all the boys with girls in a way that minimizes the sum of the absolute difference between the boy's chocolates and the girl's candies. It is acceptable if some girls remain unpaired.

Input Format

The first line contains two integers N and M.
The second line contains N integers representing the number of chocolates each boy has.
The third line contains M integers representing the number of candies each girl has.
(M >= N)

Output Format

The output should consist of a single line containing the required sum of absolute differences.

Example

Input

2 5
4 5
1 2 3 4 5

Output

0

Constraints

1 <= N <= 5000

1 <= M <= 5000

M >= N

1 <= chocolates <= 1000000

1 <= candies <= 1000000

1 <= M <= 5000

M >= N

1 <= chocolates <= 1000000

1 <= candies <= 1000000

Loading...

View Submissions

Console