分数: 100 点
问题陈述
太郎的暑假明天开始,他决定现在就开始计划。
假期包括 N 天。 对于每个 i (1 \leq i \leq N),太郎将选择以下活动之一并在 i第一天:
- A:在海里游泳。增益 a_i 点幸福。
- B:到山里捉虫子。增益 b_i 点幸福。
- C:在家做作业。增益 c_i 点幸福。
由于太郎很容易感到无聊,他无法连续两天或以上进行相同的活动。
找出太郎获得的最大可能的幸福总分。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq a_i, b_i, c_i \leq 10^4
输入
输入由标准输入按以下格式给出:
N a_1 b_1 c_1 a_2 b_2 c_2 : a_N b_N c_N
输出
打印太郎获得的最大可能的幸福总分。
示例输入 1
3 10 40 70 20 50 80 30 60 90
示例输出 1
210
如果太郎按照C、B、C的顺序进行活动,他将获得 70 + 50 + 90 = 210 点幸福。
示例输入 2
1 100 10 1
示例输出 2
100
示例输入 3
7 6 7 8 8 8 3 2 5 2 7 8 6 4 6 8 2 3 4 7 5 1
示例输出 3
46
太郎应该按照C、A、B、A、C、B、A的顺序进行活动。