Presents

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 1 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 (1,2,3), and they get (0,1,1), 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:

C (the number of children) (1 ≤ C ≤ 100,000)
C lines, each with the maximum valued gift Santa's willing to give to each child (1 ≤ M_i ≤ 1,000,000,000)
(This is elf currency, not human currency!)

P (the number of presents) (C ≤ P ≤ 200,000)
P lines, each with the value of a present (1 ≤ P_i ≤ 1,000,000,000)

Output:

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 1 gets present #5 (the best he can get), child 2 present #1, and child 3 present #4.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 1.00s
Memory Limit: 32M
Added: Dec 20, 2008
Author: hansonw1

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...