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