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 present.
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 ,
and they get , the dissatisfaction level will be
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
(the number of children)
lines, each with the maximum valued gift Santa's willing to give to
each child
(This is elf currency, not human currency!)
(the number of presents)
lines, each with the value of a present
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 gets present # (the best he can get), child present #, and
child present #.
Comments