时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H想在他家门前的马路上均匀地种上一排花树，共有 \(N\) 位置（从左到右依次从1编号），由于位置的不同，同一棵树在不同位置得到的美学价值可能不太一样。

　　小H最喜欢三种花树，它们高度分别为 8,88,888。小H希望这一排树种得有层次感，所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低，并且在此条件下，小H想要你设计出一套方美学价值最大的方案。

【输入格式】

　　第一行为一个正整数 \(N\)，表示需要种的树的棵数。
　　接下来N行，每行三个不超过 10000 的正整数 \(a_i,b_i,c_i\)，分别表示了第 \(i\) 个位置种高度为 8,88,888 的树能获得的美学价值。注意：位置时从左到右依次从1编号的，因此位置 \(i\) 与 \(i+1\) 是相邻的。

【输出格式】

　　一个正整数，为最大的美学价值和。

【输入输出样例】

　Input

4 
10 30 20 
30 10 20 
30 10 20 
30 10 20

　Output

110

【样例说明】

　　第 1 至 4 个位置分别种上高度为 88,8,888,8 的树，价值最高。

【数据限制】

　　- 对于 20% 的数据，有 \(N≤10\)
　　- 对于 40% 的数据，有 \(N≤100\)
　　- 对于 60% 的数据，有 \(N≤1000\)
　　- 对于 100% 的数据，有 \(3≤N≤100000\)

【来源】

　　Mr.he