题目描述

$Bob$ 要给班级购买奖品，总共 $N$ 天，第 $i$ 天他可以选择购买以下三类奖品：

• A: 购买图书，班级获得 $a_i$ 点快乐值。
• B: 购买文具，班级获得 $b_i$ 点快乐值。
• C: 购买体育器材，获得 $c_i$ 点快乐值。

班主任要求连续两天不能购买相同种类的奖品，那么 $Bob$ 如何购买奖品，才能使班级总快乐值最大，请帮助他求出班级班级总快乐值的最大值。

输入格式

输入格式如下：

$n$

$a_1$ $b_1$ $c_1$

$a_2$ $b_2$ $c_2$

$\dots$

$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$

$subtask1$ : $1\le n\le 20$ , $30$ 分

$subtask2$ : $1 \le n \le 10^5$ , $70$ 分