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