Presents

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 32M

Problem type

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 \displaystyle (1-0) + (2-1) + (3-1) = 4

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

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

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

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


Comments

There are no comments at the moment.