题目描述

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

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

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

输入格式

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

接下来$n$ 行，每行 3 个不超过 10000 的正整数$a_i , b_i ,c_i$，按顺时针顺序表示了第 $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≤a_i , b≤i ,c≤i ≤10000$ ，并保证$n$一定为偶数。

来源

BCSP-X 2024 初中组 T4