На мові динозаврів шоколадні яйця називаються путами. Діно дуже полюбляє смакувати путами. Вони для нього потужні джерела енергії. Сьогодні для наступних n днів Діно придбав 2 * n пут. Він має звичку з'їдати по 1 путу ранком та ввечері. Це дає йому змогу зберігати енергію на високому рівні. Діно купив чарівні пути, які можуть давати різну енергію в залежності від часу поїдання. Відомо скільки енергії дає пута якщо її з'їсти ранком чи ввечері.

Діно бажає на протязі цих n днів з'їсти пути в такій послідовності, щоб отримати якомога більше енергії.

Знайдіть максимальну кількість енергії, яку Діно може отримати.

Вхідні дані

В першому рядку записано кількість днів n (1 ≤ n ≤ 105). В кожному із наступних 2 * n рядках записані два натуральних числа si та ai (1 ≤ si, ai ≤ 109), які вказують енергію для пути, якщо з'їсти ранком чи ввечері відповідно.

Вихідні дані

Виведіть максимальну кількість енергії, яку Діно може отримати.