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

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

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

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

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

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

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

样例解释

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

数据范围

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

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

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

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

BCSP-X初中组编程能力样卷-T4

BCSP-X