eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

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

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
1 10
10 20
Çıxış verilənləri #1
10