Fine Optimization
InterviewTime limit10sMemory limit1024 MB
Pair each speed value K with one service number R so that the sum of the concatenated digit strings is as small as possible, then print that minimum.
Problem
Nobody likes being caught speeding. Worse, fines in Bajtocja are very harsh, and the system for assigning them is fairly complicated.
Each violation is recorded as a pair . is how many units over the speed limit the driver went, and is the service number of the officer who issued the ticket. The fine amount is the digits of and written next to each other. For example, if and , the amount is .
Bajtazar has just received fines. Looking at the total, he vowed never to press the gas pedal in his Alfa Bitteo again. But to keep his car and eat something besides ketchup over the next year, he needs to optimize.
Two tax offices check the paid fines. The speed office checks only that the paid fines include every speed value . The officer office checks only that the service numbers match. Nobody checks the order in which the fines were paid or how the numbers were grouped into pairs. That can change the total. A clever road offender like Bajtazar can join and differently from the original pairing so that the total is as small as possible. Can you help him?
Write a program that reads the speed values and the service numbers , computes the smallest possible total amount when each is optimally matched with one , and prints the result to standard output.
Input
The first line contains one natural number (), the number of fines Bajtazar received.
The second line contains natural numbers (), the speed values.
The third line contains natural numbers (), the service numbers of the officers who caught Bajtazar driving carelessly.
Output
The only line of output contains one natural number, the minimum total amount to pay when the speed values and service numbers are optimally matched.