题目描述

明日から太郎君の夏休みが始まります。 太郎君は夏休みの計画を立てることにしました。

夏休みは $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$

输出格式

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

题目大意

太郎的暑假有$n$天，第$i$天他可以选择做以下三种事情：

1. 游泳，获得$a_i$点幸福值。
2. 捉虫，获得$b_i$点幸福值。
3. 写作业，获得$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\ \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 の順に活動を行えばよいです。