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