e-olymp
Competitions

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

Дино и путы

123.jpg

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

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

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

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

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

Ограничения

  • 1 ≤ n ≤ 105
  • 1 ≤ si, ai ≤ 109
Time limit 1 second
Memory limit 64 MiB
Input example #1
1
5 6
4 3

Output example #1
10
Input example #2
2
3 6
7 1
4 9
10 11

Output example #2
32