e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Azərbaycan Respublika Olimpiadasının yarımfinalı 2019-2020

Дино и путы

123.jpg

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

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

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

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

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

В первой строке указано количество дней n (1n105). В каждой из следующих 2 * n строках указаны два целых числа si и ai (1si, ai109), обозначающих энергию для путы, съеденной утром и вечером соответственно.

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
1
5 6
4 3

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

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