eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Капризные дети

Капризные дети

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Няня укладывает спать детей. Но самой ей поспать никак не удается: не успевает она уложить спать одних, как просыпаются другие…

У няни N детей, и все они очень разные. Она уже запомнила, сколько минут ей нужно, чтобы уложить спать k-го ребенка (обозначим это время через a_k), и сколько минут после этого он будет спать (обозначим это время через b_k). Сама няня может спать, только когда спят все дети.

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

Например, пусть есть всего 2 ребенка: a_1=1, b_1=10, a_2=10, b_2=20. Если она сначала начнет укладывать первого ребенка, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго, то затем она успеет уложить первого и получит целых 10 минут отдыха.

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

Первая строка содержит N (1N100000). Вторая строка содержит натуральные числа a_1a_n , третья - b_1b_n . Числа не превосходят 10^9 и отделяются друг от друга пробелами.

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

Единственная строка должна содержать число T, равное максимально возможному времени сна няни, либо 0, если ей поспать не удастся.

Пример

Входные данные #1
2
1 10
10 20
Выходные данные #1
10