778. Valentine's Matchmaking

0

Medium

Today is Valentine's Day in Russia, where the number of girls is greater than the number of boys. As the evening's anchor, your goal is to pair each boy with a girl in a way that minimizes the sum of the absolute differences between their chocolates and 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

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