cho.sh
Notes
Loading...

Minimum Pairing Cost for Two Sets

Time limit

2s

Memory limit

128 MB

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.