수 집합 맞추기 (Hard)

음이 아닌 정수로 이루어진 두 집합 S와 T가 주어진다. S의 원소 s와 T의 원소 t를 골라 몇 개의 쌍 (s, t)를 만들려고 한다.

선택한 쌍들은 다음 조건을 모두 만족해야 한다.

1. S의 어떤 원소도 T의 어떤 원소와 쌍을 이룰 수 있고, T의 어떤 원소도 S의 어떤 원소와 쌍을 이룰 수 있다.
2. S의 모든 원소는 적어도 하나의 쌍에 포함되어야 하며, T의 모든 원소도 적어도 하나의 쌍에 포함되어야 한다.

쌍 (a, b)의 비용은 |a - b|이다. 전체 비용은 선택한 모든 쌍의 비용을 합한 값이다.

S와 T가 주어졌을 때 만들 수 있는 최소 전체 비용을 구하시오.

첫째 줄에 S의 원소 개수 N과 T의 원소 개수 M이 공백으로 구분되어 주어진다.

둘째 줄에는 S의 원소 N개가 증가하는 순서로 주어진다. 셋째 줄에는 T의 원소 M개가 증가하는 순서로 주어진다.

각 집합의 원소 개수는 500,000 이하이다. 모든 원소는 0 이상 1,000,000,000 이하의 정수이다.

가능한 최소 전체 비용을 출력한다.