题目描述

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

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

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

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

输入格式

第一行输入 $N$

接下来 $N$ 行，每行输入三个整数分别为 $a_i,b_i,c_i$。

输出格式

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

3
10 40 70
20 50 80
30 60 90

210

1
100 10 1

100

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

46

提示

样例 1 解释

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

样例 3 解释

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

数据范围

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