假期计划 - 代码源竞赛平台

题目描述

蜗蜗准备度过一个为期 $N$ 天的假期。第 $i$ 天可以从以下三项活动中选择一项：

• 进行活动 A，获得 $a_i$ 点快乐值；
• 进行活动 B，获得 $b_i$ 点快乐值；
• 进行活动 C，获得 $c_i$ 点快乐值。

为了避免连续进行相同的活动，相邻两天不能选择同一项活动。请你求出整个假期能获得的最大快乐值。

输入格式

第一行包含一个整数 $N$，表示假期天数。

接下来 $N$ 行，每行包含三个整数 $a_i$、$b_i$、$c_i$，表示第 $i$ 天进行三项活动分别获得的快乐值。

输出格式

输出一行一个整数，表示最大快乐值。

样例

3
10 40 70
20 50 80
30 60 90

210

样例解释

可以依次选择活动 C、活动 B、活动 C，获得 $70+50+90=210$ 点快乐值。

数据范围

对于 100% 的数据，保证 $1\le N\le 10^5$，$0\le a_i,b_i,c_i\le 10^4$。