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

Условие

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

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

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

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

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

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

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

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

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

3
1 1
2 2
3 3

9