Under construction

Still being built. Things may change

Fine Optimization

Interview

Time limit10sMemory limit1024 MB

Summary
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.
Level

Medium5 of 10

Topics
Greedy, Sorting
Solved
No attempts yet

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 (Ki,Ri)(K_i, R_i). KiK_i is how many units over the speed limit the driver went, and RiR_i is the service number of the officer who issued the ticket. The fine amount is the digits of KiK_i and RiR_i written next to each other. For example, if Ki=12K_i = 12 and Ri=5432R_i = 5432, the amount is 125432125432.

Bajtazar has just received NN 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 KiK_i. The officer office checks only that the service numbers RiR_i 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 KiK_i and RiR_i 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 KiK_i and the service numbers RiR_i, computes the smallest possible total amount when each KiK_i is optimally matched with one RiR_i, and prints the result to standard output.

Input

The first line contains one natural number NN (1≤N≤10000001 \le N \le 1000000), the number of fines Bajtazar received.

The second line contains NN natural numbers KiK_i (1≤Ki≤1000001 \le K_i \le 100000), the speed values.

The third line contains NN natural numbers RiR_i (1≤Ri≤1000001 \le R_i \le 100000), 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.

Examples2

  1. Example 1

    Input
    3
    5 2 30
    13 9 7
    
    Expected output
    579
    
  2. Example 2

    Input
    5
    5 12 7 2 8
    1 1 1 1 1
    
    Expected output
    345