Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

KB Lo-Fi

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 255 megabytes
Time limit: 1.0 seconds

Congratulations! You've just gotten a job at the local biggest electronics store, KB Lo-Fi. You are in charge of selling the hottest new product: the J-Phone 13. Each of your J-Phones has a certain price tag. Every customer gives an asking bid - a certain price they want to pay for a J-Phone 13. They don't particularly care which specific J-Phone 13 they get (they're buying for the brand, not the product), as long it as costs less than or equal to their asking bid.

What is the maximum amount of money we can make? It's ok if you don't sell a J-Phone to everybody, as long as your revenue is maximized.

Input

The first line contains N, the number of customers.
The next N lines will each contain an integer c_i, representing the asking bid in dollars of a customer.

This will be followed by a line containing M, the number of J-Phones.
M lines will follow, each contain an integer w_i, representing the price in dollars of a specific J-Phone.

Output

Output a single integer. This should be the maximum amount of money we can make from selling some (or all) of the given J-Phones to some (or all) of the given customers.

Constraints

  • 1 \le N \le 50,000
  • 1 \le M \le 50,000
  • 1 \le c_i \le 1,000,000,000 for all customers.
  • 1 \le w_i \le 1,000,000,000 for all J-Phones.

Subtasks

  • Subtask 1 (+22%): N = 1.
  • Subtask 2 (+28%): N <= 7 and M <= 7.
  • Subtask 3 (+16%): 1 <= N <= 500.
  • Subtask 4 (+34%): No further constraints apply.

Note:

If you are using a type sensitive language such as C, C++, C#, or Java then be sure to use variables, functions, and methods that support 64-bit precision. The answer does not exceed the maximum value of a signed 64-bit integer in any test case.
64-bit integer types include long long for C and C++, and long for C# and Java. Haskell programmers are ineligible for free advice.

Sample Explanations:

Sample Input 1

In this case, we have a single customer with an asking bid of $10. We have four J-Phones priced at $8, $5, $7 and $9. The maximum money we can make is by selling the J-Phone priced at $9 to the customer, thus making $9.

Sample Input 2

In this case, we have a three customers with asking bids of $10, $9 and $8. We have three J-Phones priced at $10, $9 and $8. The maximum money we can make is by selling the $10 J-Phone to the $10 customer, the $9 J-Phone to the $9 customer, and the $8 J-Phone to the $8 customer. This gives us a total of $10 + $9 + $8 = $27.
Note that we can't sell, for example, the $10 J-Phone to the $8 customer, as it is above the customer's asking bid.

  • Sample Input 1

    1
    10
    4
    8
    5
    7
    9
    

    Sample Output 1

    9
    
  • Sample Input 2

    3
    10
    9
    8
    3
    10
    9
    8
    

    Sample Output 2

    27