题目描述

古埃及法王有着一个巨大的宝库，里面珍藏着无数价值连城的珠宝。由于觊觎宝库的坏 蛋 很多，因此法王邀请你帮他设计一个环形的防守圈，来抵御强盗的入侵。他想在宝库周 围均匀地布置上 n 个炮塔（注意：由于是环形，首尾相接，第一个炮塔和第 n 个炮塔是 相邻的），塔防的位置很重要，每个位置适合摆的炮塔都不一样，也就是说每个位置摆放不 同的炮塔获得的战斗力是不同的。

如第一个位置摆放三种炮塔获得的战斗力分别是：1，3，2，此时摆放中射炮获得的战 斗力最高；而第二个位置摆放三种炮塔获得的战斗力分别是：3，1，2，此时摆放低射炮获 得的战斗力最高。

我们的军火库中有三种炮塔，分别为低射对地炮，中射迫击炮以及高射对空炮。法王希 望这一圈炮塔摆的很有层次感，所以任何一个位置的炮塔要比它相邻的两个炮塔的高度都高 或者都低（高射炮>中射炮>低射炮），并且在此条件下，法王想要你设计出一套方案，使 得防御力也就是战斗力最高。

输入格式

第一行为一个正整数 n，表示需要摆的炮塔个数。

接下来 n 行，每行 3 个不超过 10000 的正整数 i i i a ,b ,c ，按顺时针顺序表示了第 i 个位置摆低射,中射以及高射炮能获得的战斗力。

第 i 个位置的炮塔与第 i+1 个位置的炮塔相邻，特别地，第 1 个位置的炮塔与第 n 个位置的炮塔相邻。

输出格式

一个正整数，为最大的战斗力之和。

4
1 3 2
3 1 2
3 1 2
3 1 2

11

样例解释

第 1 至 n 个位置分别摆上高度为中射,低射,高射,低射炮，战斗力最高

数据范围

对于 20% 的数据，有 n≤10；

对于 40% 的数据，有 n≤100；

对于 60% 的数据，有 n≤1000；

对于 100% 的数据，有 4≤n≤100000，1≤ ai ,bi ,ci ≤10000 ，并保证 n 一定为偶数。