AT_dp_c Vacation

题目描述

暑假有 $N$ 天。对于每一天 $i$（$1 \leq i \leq N$），太郎君可以选择以下活动之一：

• A：在海里游泳，获得幸福度 $a _ i$。
• B：在山上抓虫，获得幸福度 $b _ i$。
• C：在家做作业，获得幸福度 $c _ i$。

由于太郎君容易厌倦，他不能连续两天及以上做同样的活动。

请计算太郎君可以获得的最大总幸福度。

输入格式

输入以以下格式从标准输入中提供：

$N$
$a _ 1$ $b _ 1$ $c _ 1$
$a _ 2$ $b _ 2$ $c _ 2$
$\ldots$
$a _ N$ $b _ N$ $c _ N$

输出格式

输出太郎君可以获得的最大总幸福度。

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 10 ^ 5$
• $1 \leq a _ i, b _ i, c _ i \leq 10 ^ 4$

样例解释 1

按顺序选择活动 C, B, C，可以获得的总幸福度为 $70 + 50 + 90 = 210$。

样例解释 3

按顺序选择活动 C, A, B, A, C, B, A 可以获得最大总幸福度。

Translated by User 735713.

输入输出样例 #1

输入 #1

3
10 40 70
20 50 80
30 60 90

输出 #1

210

输入输出样例 #2

输入 #2

1
100 10 1

输出 #2

100

输入输出样例 #3

输入 #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