Description

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

• 如果在第i天运动，得xi​分；
• 如果在第i天学习，得yi​分；
• 如果在第i天休息，得zi​分。

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

Input Format

第一行：单个整数n

第二行到第n+1行：第i+1行有三个整数xi​，yi​与zi​。

Output Format

单个整数：表示最大分数

3
100 1 1
1 100 1
1 1 100

300

Hint

数据范围

• 30%的分数，1≤n≤10

• 60%的分数，1≤n≤300

• 100%的分数，1≤n≤200,000

• 0≤xi≤10,000

• 0≤yi≤10,000

• 0≤zi≤10,000

Source