题目描述

假期共有 $n$ 天，每天可以在三件事中选择做一件事：

• 如果在第 $i$ 天运动，得 $x_i$ 分；
• 如果在第 $i$ 天学习，得 $y_i$ 分；
• 如果在第 $i$ 天休息，得 $z_i$ 分。

在假期里，要求每天做的事情不能与前一天重复，如何安排假期活动，才能使总分最大？

输入格式

• 第一行：单个整数 $n$
• 第二行到第 $n+1$ 行：第 $i+1$ 行有三个整数 $x_i$，$y_i$ 与 $z_i$。

输出格式

• 单个整数：表示最大分数

数据范围

• $30\%$ 的分数，$1\leq n\leq 10$
• $60\%$ 的分数，$1\leq n\leq 300$
• $100\%$ 的分数，$1\leq n\leq 200,000$
• $0\leq x_i\leq 10,000$
• $0\leq y_i\leq 10,000$
• $0\leq z_i\leq 10,000$

样例数据

输入:

3
100 1 1
1 100 1
1 1 100

输出:

300