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.

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_c 明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。 夏休みは $ N $ 日からなります。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、$ i $ 日目には太郎君は次の活動のうちひとつを選んで行います。 - A: 海で泳ぐ。 幸福度 $ a_i $ を得る。 - B: 山で虫取りをする。 幸福度 $ b_i $ を得る。 - C: 家で宿題をする。 幸福度 $ c_i $ を得る。 太郎君は飽き性なので、$ 2 $ 日以上連続で同じ活動を行うことはできません。 太郎君が得る幸福度の総和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ : $ $ a_N $ $ b_N $ $ c_N $

太郎君が得る幸福度の総和の最大値を出力せよ。

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\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ a_i,\ b_i,\ c_i\ \leq\ 10^4 $ ### Sample Explanation 1 C, B, C の順に活動を行うと、幸福度の総和は $ 70\ +\ 50\ +\ 90\ =\ 210 $ となります。 ### Sample Explanation 3 C, A, B, A, C, B, A の順に活動を行えばよいです。