题目描述

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

• 如果在第 $i$ 天选择玩耍，则可以获得 $x_i$ 点分数
• 如果在第 $i$ 天选择刷题，则可以获得 $y_i$ 点分数
• 如果在第 $i$ 天选择躺平，则可以获得 $z_i$ 点分数

如果要求每天做的事情不能与前一天相同，则如何安排假期的活动，才能使得分数之和达到最大？

输入格式

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

输出格式

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

3
100 1 1
1 100 1
1 1 100

300

数据范围

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