Under construction

Still being built. Things may change

Bizmarket

Interview

Time limit2sMemory limit1024 MB

Summary
Match items to client companies, at most one each, to maximize the sum of (A_i - B_j) over matched pairs, where a pair counts only if A_i is at least B_j.
Level

Medium4 of 10

Topics
Greedy, Sorting
Solved
No attempts yet

Problem

Bizmarket is an online general trading company that mainly serves businesses. It runs a welfare mall, corporate promotion and gift business, and industrial goods distribution. Beyond these core areas, it also runs brand, rental, and energy businesses. Its guiding principle is "contributing to the efficiency of client companies' operations and pursuing the welfare of their members." Shinuk was asked by Bizmarket to help run its rental business efficiently.

Bizmarket has NN items and MM client companies that want to rent them. Each item ii has a satisfaction value AiA_i, and each client company jj wants to rent an item by paying BjB_j. Each client company can rent only one item, and each item can be rented to only one client company.

If an item with satisfaction AiA_i is rented to a client company that pays BjB_j, the client gains Ai−BjA_i - B_j of client satisfaction. Every client company wants to get at least what it pays, so if the client satisfaction would drop below 00, the company does not go through with the deal. Without a deal, no client satisfaction is gained.

Shinuk's task is to assign items to the client companies so that the total client satisfaction is maximized. He had too many assignments, so he handed this job to you and left. Compute the maximum total client satisfaction on his behalf.

Input

The first line contains the integers NN and MM, separated by a space. (1≤N,M≤2×105)(1 \le N, M \le 2 \times 10^5)

The second line contains NN integers A1,A2,…,ANA_1, A_2, \dots, A_N, separated by spaces. (0≤Ai≤109)(0 \le A_i \le 10^9)

The third line contains MM integers B1,B2,…,BMB_1, B_2, \dots, B_M, separated by spaces. (0≤Bj≤109)(0 \le B_j \le 10^9)

Output

On the first line, print the maximum total client satisfaction that can be obtained by choosing an item for each client company.

Hint

The answer can exceed the int range, so you must use a 64-bit integer type (C/C++: long long, Java: long).

Examples2

  1. Example 1

    Input
    5 5
    6 7 8 9 10
    2 3 4 5 6
    
    Expected output
    20
    
  2. Example 2

    Input
    5 3
    927291536 144432154 222251432 846751354 648975123
    105423157 28465 1354216
    
    Expected output
    2316212175