题目描述

小苯面前有 n 盏灯排成一排，每盏灯都有“蓝”和“黄”两种可选的颜色，分别用(xi, yi)对描述每盏灯，如果第i盏灯打开了“蓝色”，则可以获得xi分，如果打开了“黄色”，则可以获得yi分。如果不点亮该灯，则不得分。

现在大白熊想让小苯选择一些灯点亮，但需要满足：如果有两盏相邻的灯同时被点亮，则其两者的颜色必须不同。

现在小苯想知道，如果他按照最优方案点灯，最多可以获得多少分，请你帮帮他吧。

输入描述

输入包含 n+1 行。

第一行一个正整数 n 表示灯的个数。

接下来n行，每行两个正整数xi, yi，描述每盏灯点亮时的对应得分。

1 <= n <= 1e5;

1 <= xi, yi <= 1e9.

输出描述

输出一行一个整数表示小苯的最大得分。

输入示例

4
1 3
4 3
5 6
2 3

输出示例

15

提示信息

第1, 2, 3, 4盏灯分别点亮“黄”，“蓝”，“黄”，“蓝”，得分为：3 + 4 + 6 + 2 = 15，可以证明为最优方案。

时间限制：c/c++：1s；java：5s；其他语言：3s。