配点 : $100$ 点

問題文

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

夏休みは $N$ 日からなります。 各 $i$ ($1 \leq i \leq N$) について、$i$ 日目には太郎君は次の活動のうちひとつを選んで行います。

• A: 海で泳ぐ。 幸福度 $a_i$ を得る。
• B: 山で虫取りをする。 幸福度 $b_i$ を得る。
• C: 家で宿題をする。 幸福度 $c_i$ を得る。

太郎君は飽き性なので、$2$ 日以上連続で同じ活動を行うことはできません。

太郎君が得る幸福度の総和の最大値を求めてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 10^5$
• $1 \leq a_i, b_i, c_i \leq 10^4$

入力

入力は以下の形式で標準入力から与えられる。

$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

C, B, C の順に活動を行うと、幸福度の総和は $70 + 50 + 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

C, A, B, A, C, B, A の順に活動を行えばよいです。