Байтландия, как известно, страна с развитыми торговыми отношениями.
Аркадий Павлович решил попробовать заняться торговлей и подзаработать себе на отпуск продажей компьютерной техники. Для этого ему необходимо закупать технику у других продавцов. Прежде чем начать работу, он решил понаблюдать за происходящим на рынке Байтландии и придумать, как получать наибольшую прибыль.
Аркадий Павлович узнал, что каждый продавец продаёт один компьютер, и каждый покупатель готов купить ровно один компьютер. Всего на рынке торгуют N продавцов, стоимость компьютера у i-го из них равна Ai монет, причём цены могут отличаться у разных продавцов. Кроме того, он нашёл для себя M потенциальных покупателей, каждый из которых хочет купить компьютер за Bi монет. При этом сам Аркадий Павлович может купить и продать любое количество компьютеров.
Аркадию Павловичу необходимо получить наибольшую прибыль (выгодно купить и выгодно продать). Поэтому он обратился за помощью к Вам – лучшему программисту Байтландии.
Входные данные:
Первая строка входного файла содержит разделенные одиночным пробелом два целых числа N, M (1 ≤ N, M ≤ 105) – количество продавцов на рынке Байтландии и количество потенциальных покупателей соответственно.
Вторая строка содержит N целых чисел Ai (0 ≤ Ai ≤ 109), разделённых одиночными пробелами, – стоимости, по которым продавцы готовы продавать компьютеры.
Третья строка содержит M целых чисел Bi (0 ≤ Bi ≤ 109), разделённых одиночными пробелами, – суммы, которые потенциальные покупатели готовы отдать при покупке компьютера.
Выходные данные:
Первая и единственная строка выходного файла должна содержать одно целое число S – размер максимальной выгоды в монетах, которую может получить Аркадий Павлович.
Примеры:
№
input.txt
output.txt
1
2 3
1 1
3 3 3
4
2
6 5
5 10 8 4 7 2
3 1 11 18 9
27
Сложность задачи: 100%
Разбор задачи
Пример 1. Аркадий Павлович купит компьютеры у 1-го и 2-го продавцов и продаст их любым двум покупателям.
Пример 2.
Наиболее выгодно купить компьютеры у 1-го, 4-го и 6-го продавцов и продать 3-ему, 4-ому и 5-ому покупателям.
