Making Couples
Time limit2sMemory limit128 MB
Given lists of men's and women's personality values, form min(n, m) man-woman couples that minimize the total absolute difference of matched values.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Sorting, Greedy, Array
- Solved
- No attempts yet
Problem
There are n men and m women who do not currently have partners. Each person's personality is represented by a natural number.
A couple must consist of one man and one woman. First, make as many couples as possible. Then, among those maximum-size matchings, minimize the sum of the absolute differences between the two personality values in each couple. The number of couples that must be made is min(n, m).
Input
The first line contains two integers n and m (1 <= n, m <= 1,000).
The second line contains the personality values of the n men. The third line contains the personality values of the m women. Each personality value is a natural number not greater than 1,000,000.
Output
Print the minimum possible sum of personality-value differences.