Minimum Pairing Cost for Two Sets

Time limit2sMemory limit128 MB

Summary
Given two sorted sets S and T, choose pairs (one element from each) so every element in both sets appears in some pair, minimizing the total sum of |a-b| over chosen pairs.
Level

Hard8 of 10

Topics
Dynamic programming, Greedy, Sorting, Math
Solved
No attempts yet

Problem

You are given two sets S and T of nonnegative integers. A pair consists of one element from S and one element from T, and you may choose any number of pairs.

The chosen pairs must satisfy both conditions below.

  1. Every element of S must appear in at least one pair.
  2. Every element of T must also appear in at least one pair.

The cost of a pair (a, b) is |a - b|. Find the minimum possible sum of costs over all chosen pairs.

Input

The first line contains the number of elements in S and the number of elements in T, separated by a space.

The second line contains the elements of S, and the third line contains the elements of T. Each line is given in increasing order.

Each set has at most 50,000 elements. Every element is an integer between 0 and 100,000 inclusive.

Output

Print the minimum possible total cost when every element is included in at least one chosen pair.

Examples1

  1. Example 1

    Input
    5 6
2 8 9 10 11
0 3 4 6 7 11
    Expected output
    10