| Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
В маленькой IT компании сейчас ведётся проект, который нужно закрыть в кратчайшие сроки. Для этого были привлечены два специалиста: один занимается кодированием, а второй — развертыванием.
Чтобы закрыть проект, нужно разработать и развернуть на сервере N фичей, у каждой фичи есть два времени: время, необходимое для кодирования и время, необходимое для развертывания. Каждый специалист может работать только с одной фичей в один момент времени. Также, специалист не может перейти к следующей фиче, не закончив работу с текущей. Разработка фичи обязательно должна начинаться с кодирования, и только после того, как фича была закодирована, её можно начинать развёртывать.
Чтобы закрыть проект в кратчайшие сроки нужно распределить разработку и развёртывание фич оптимальным способом. Напишите программу, которая найдет оптимальный порядок обработки фич и выведет минимальное время.
В первой строке записано целое число N (1 ≤ N ≤ 105) — количество фич.
Следующие N строк содержат описание фич. Каждая строка содержит два целых числа t1 и t2 (1 ≤ t1, t2 ≤ 109) — время, необходимое на кодирование и развертывание фичи соответственно.
В первой строке выведите минимальное время, необходимое для обработки всех фич.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|