Задача K. Маленькая IT компания

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

В маленькой IT компании сейчас ведётся проект, который нужно закрыть в кратчайшие сроки. Для этого были привлечены два специалиста: один занимается кодированием, а второй — развертыванием.

Чтобы закрыть проект, нужно разработать и развернуть на сервере N фичей, у каждой фичи есть два времени: время, необходимое для кодирования и время, необходимое для развертывания. Каждый специалист может работать только с одной фичей в один момент времени. Также, специалист не может перейти к следующей фиче, не закончив работу с текущей. Разработка фичи обязательно должна начинаться с кодирования, и только после того, как фича была закодирована, её можно начинать развёртывать.

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

Формат входных данных

В первой строке записано целое число N (1 ≤ N ≤ 105) — количество фич.

Следующие N строк содержат описание фич. Каждая строка содержит два целых числа t1 и t2 (1 ≤ t1, t2 ≤ 109) — время, необходимое на кодирование и развертывание фичи соответственно.

Формат выходных данных

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

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

Стандартный вход Стандартный выход
1
3
1 1
2 2
3 3
9

0.070s 0.008s 13