eolymp
Задачи

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

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

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

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

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

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

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

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

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

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

Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
2
1 10
10 20
Выходные данные #1
10