Распределение

prb179

Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов N различных отрядов, которые были отправлены на завоевания. Однако прибывшие лишь только сейчас разведчики донесли о силах противников, скопленных в этих поселениях, что естественно скорректировало планы Оргрима. И теперь он хочет произвести перераспределение войск по отрядам, переводя воинов из одного отряда в другой. При этом, чтобы не создавать неразбериху в рядах своей армии и выполнить перераспределение как можно быстрее, количество таких переводов должно быть минимально возможным (за один раз переводится один солдат из некоторого отряда в другой).

Напишите программу, которая определяет минимальное количество переводов для перераспределения войск.

Технические условия

Входные данные

Первая строка входного файла содержит целое число N (1 ≤ N ≤ 10000) – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – N чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает 10⁶. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

Выходные данные

В выходной файл выведите минимально возможное количество переводов.

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 0.666667
Сложность: 10% 111/124

Пример

Пример входных данных

Sample 1
3
5 8 10
5 8 10

Sample 2
2
6 7
5 8

Sample 3
5
1 2 3 4 5
2 3 4 5 1

Sample 4
5
1 2 3 2 1
0 0 9 0 0

Пример выходных данных

Sample 1
0



Sample 2
1



Sample 3
4



Sample 4
6

← Каждый третий бесплатно

Список задач