题目描述

小 A 计划连续安排接下来 $n$ 天的活动。每天可以从三种活动中恰好选择一种：

• 活动 $A$；
• 活动 $B$；
• 活动 $C$。

对于第 $i$ 天：

• 选择活动 $A$ 可以获得快乐值 $a_i$；
• 选择活动 $B$ 可以获得快乐值 $b_i$；
• 选择活动 $C$ 可以获得快乐值 $c_i$。

为了避免过于单调，相邻两天不能选择同一种活动。

请你求出：在满足限制的前提下，连续安排这 $n$ 天活动所能获得的最大快乐值。

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行，每行输入三个整数 $a_i,b_i,c_i$。

数据范围：

$$1 \le n \le 2\times 10^5$$ $$1 \le a_i,b_i,c_i \le 10^9$$

输出格式

输出一个整数，表示最大快乐值。

3
10 40 70
20 50 80
30 60 90

210

Hint

样例解释： 一种最优安排为：

• 第 $1$ 天选活动 $C$，得到 $70$；
• 第 $2$ 天选活动 $B$，得到 $50$；
• 第 $3$ 天选活动 $C$，得到 $90$。

总快乐值为：

$$70+50+90=210$$