eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дино и путы

Дино и путы

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
123.jpg

На языке динозавров нарисованные выше шоколадные яйца называются путами. Дино очень любит кушать путы. Они для него настоящий источник энергии, также он собирает коллекцию игрушек, которые выходят их них.Сегодня для следующих n дней Дино купил 2 * n пута. Он превратил в привычку съедать по 1 путе утром и вечером. Это позволяет ему сохранять энергию на высоком уровне.

Дино купил волшебные путы, которые могут дать разную энергию в зависимости от того съедены ли, они утром или вечером. Нам известно сколько энергии дает пута съеденная как утром так и вечером.

Дино очень умный и он в течении этих n дней планирует съесть эти путы в такой последовательности, чтобы в конце получить от них максимум энергии.

Найдите максимальное количество энергии, которое Дино может получить.

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

В первой строке указано количество дней n (1n10^5). В каждой из следующих 2 * n строках указаны два целых числа s[i] и a[i] (1s[i], a[i]10^9), обозначающих энергию для путы, съеденной утром и вечером соответственно.

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

Выведите максимальное количество энергии, которое Дино может получить.

Пример

Входные данные #1
1
5 6
4 3

Выходные данные #1
10
Входные данные #2
2
3 6
7 1
4 9
10 11

Выходные данные #2
32
Источник Полуфинал Республиканской олимпиады Азербайджана 2019-2020