小码王双城接力赛

题目背景

小码王要举办一场北京校区和深圳校区联合参加的趣味信息学赛。

舞台上一共有 N 轮互动抢答。每一轮都必须派出一位同学上场：

• 如果这一轮由 北京 的同学上场，可以获得 b_i 点热力值；
• 如果这一轮由 深圳 的同学上场，可以获得 s_i 点热力值。

为了体现“联合赛”的精神，不允许同一个城市连续上场 3 轮。

请你帮小码王安排每一轮由哪个城市的同学上场，使总热力值最大。

输入格式

第一行一个整数 N，表示互动抢答的轮数。

接下来 N 行，每行两个整数 b_i, s_i，分别表示第 i 轮由北京同学上场、深圳同学上场时可以获得的热力值。

输出格式

输出一个整数，表示可以获得的最大总热力值。

样例输入

5
7 15
13 14
7 14
12 14
3 4

样例输出

59

样例说明

一种最优安排是：

• 第 1 轮：深圳
• 第 2 轮：北京
• 第 3 轮：深圳
• 第 4 轮：深圳
• 第 5 轮：北京

总热力值为：

15 + 13 + 14 + 14 + 3 = 59

注意：规则是 不能连续 3 轮都由同一个城市上场，并不是必须严格交替。

数据范围

• 1 <= N <= 200000
• 0 <= b_i, s_i <= 10^9

提示

根据小码王房屋涂色题目改的

可以设计状态：

• dp[i][0][1]：前 i 轮结束后，第 i 轮选北京，且北京当前连续出现 1 次的最大值
• dp[i][0][2]：前 i 轮结束后，第 i 轮选北京，且北京当前连续出现 2 次的最大值
• dp[i][1][1]：前 i 轮结束后，第 i 轮选深圳，且深圳当前连续出现 1 次的最大值
• dp[i][1][2]：前 i 轮结束后，第 i 轮选深圳，且深圳当前连续出现 2 次的最大值

转移时分类讨论“换城市”还是“继续同城市”即可。