Vacation
题意翻译
太郎的暑假有$n$天，第$i$天他可以选择做以下三种事情：
1. 游泳，获得$a_i$点幸福值。
2. 捉虫，获得$b_i$点幸福值。
3. 写作业，获得$c_i$点幸福值。
但他不能连续两天进行同一种活动，请求出最多可以获得多少幸福值。
题目描述
[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 $
输出格式
太郎君が得る幸福度の総和の最大値を出力せよ。
输入输出样例
输入样例 #1
3
10 40 70
20 50 80
30 60 90输出样例 #1
210输入样例 #2
1
100 10 1输出样例 #2
100输入样例 #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说明
### 制約
- 入力はすべて整数である。
- $ 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 の順に活動を行えばよいです。