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

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

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

输入包含 n+1 行。

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

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

1 <= n <= 1e5;

1 <= x_i, y_i <= 1e9.

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

4
1 3
4 3
5 6
2 3

15

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

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