It's that time of year again, and Santa needs to figure out what gift to give to every child on Earth.
He's made a list, and he's checked it twice, and he's already found out
who's naughty or nice.
Based on this information, he's determined the maximum quality gift he's
willing to give to each child.
However, Santa and his elves don't custom craft gifts anymore – he runs
a nice little industrial operation.
As such, he has a bunch of pre-made presents, each with a certain
value.
Now, each child should get exactly
Santa wants to make the children as happy as possible.
Let's call the dissatisfaction level the sum of the differences
between what a child gets and what he should get.
For example, if the children should get presents valued at most
He wants to find an assignment that minimizes this dissatisfaction.
This is no easy task, though, and of course he'd rather have a computer
program to do it.
Help Santa give out presents fairly!
Input Specification
(This is elf currency, not human currency!)
Output Specification
The minimum dissatisfaction level of any present assignment.
If it's impossible to assign presents, output -1
.
Sample Input
3
80
90
100
5
70
40
50
60
80
Sample Output
60
The kids should be reasonably happy this year!
One possible arrangement:
Child
Comments