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

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

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

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

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

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

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

【样例解释】

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

【数据范围】

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

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

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

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