问题陈述

太郎的暑假明天就开始了，他决定现在就制定计划。

假期有 $N$ 天。每 $i$ ( $1 \leq i \leq N$ )天，太郎将从下面的活动中选择一项，并在 $i$ 这一天进行：

• A: 在海里游泳。获得 $a_i$ 点快乐值。
• B: 在山上捉虫子。获得 $b_i$ 点快乐。
• C: 在家做作业。获得 $c_i$ 点快乐。

由于太郎很容易感到无聊，所以他不能连续两天或两天以上做同样的活动。

求太郎可能获得的幸福总分的最大值。

限制因素

• 输入值均为整数
• $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 的顺序开展活动。

来源

https://atcoder.jp/contests/dp/tasks/dp_c