Задача G. Жребий Крижановского

Автор:Восьмая всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:game.in   Ограничение памяти:256 Мб
Выходной файл:game.out  

Условие

Петя играет с друзьями в игру, которую иногда называют "Жребий Крижановского". Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.

Петя с друзьями при игре просто называют по очереди загаданные ими числа, а потом определяют, кто выиграл, и подсчитывают баллы. Однако при таком формате игры в принципе можно сжульничать, не загадывая число заранее, а, уже зная числа, названные предыдущими игроками, выбрать себе оптимальное "загаданное" число. Этим и пользуется Петя. Он называет число последним и старается выбрать число так, чтобы максимизировать свой выигрыш.

Идет последний тур игры. Известны очки всех игроков перед этим туром и названные игроками числа. Выясните, какое число следует назвать Пете, чтобы по результатам игры у как можно большего числа игроков количество баллов было меньше чем у него. Если таких чисел несколько, то Петя хочет назвать минимальное возможное.

Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.

Формат входного файла

Первая строка входного файла содержит число n — количество игроков. Вторая строка содержит n чисел — баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). Третья строка содержит n − 1 число — числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.

Формат выходного файла

Выведите в выходной файл число, которое следует назвать Пете.

Во втором примере Петя не может выиграть в последнем туре. Однако, назвав число 2, Петя не позволяет выиграть первому игроку, и тем самым остается вторым по итогам всей игры. У четырех игроков баллы меньше чем у Пети.

Ограничения

2 ≤ n ≤ 100

Примеры тестов

Входной файл (game.in) Выходной файл (game.out)
1
6
0 0 0 0 0 0
2 3 4 5 6
1
2
6
8 3 12 5 0 9
2 1 3 1 4
2

0.032s 0.006s 15