Maximizing the Ornamental Value in a Circular Garden

The master has a circular garden and wants to plant n trees evenly around it. He has three favorite types of trees with heights \(10\), \(20\), and \(30\). However, each spot in the garden has unique soil conditions, so the ornamental value of planting a particular tree type varies from position to position. In some cases, a tree may lose some of its ornamental charm if planted in an unsuitable spot.

The master desires an arrangement that exhibits a layered, alternating pattern. Specifically, for every tree planted, its height must be either strictly greater than both of its immediate neighbors or strictly less than both. Mathematically, if the height at position \(i\) is \(h_i\) (with indices taken modulo \(n\)), then for every \(i\) we must have either \[ h_i > h_{i-1} \quad \text{and} \quad h_i > h_{i+1} \] or \[ h_i < h_{i-1} \quad \text{and} \quad h_i < h_{i+1} \] Since only two different heights can alternate in a circle without creating conflicts, the final valid arrangement will choose exactly two of the three tree types and assign them alternately around the circle.

You are given the ornamental value for planting each of the three types (with heights \(10, 20, 30\)) at each position. Your task is to choose a valid alternating arrangement (i.e. select two distinct tree types and decide which one starts at position 0) so as to maximize the total ornamental value of the garden.

inputFormat

The first line contains an integer \(n\) (\(n \ge 2\)), the number of positions in the garden.

The next \(n\) lines each contain three space-separated integers. The three integers on the \(i\)-th line represent the ornamental value obtained by planting a tree of height \(10\), \(20\), and \(30\) respectively at that position.

outputFormat

Output a single integer: the maximum total ornamental value achievable under the alternating condition.

sample

4
5 3 4
2 10 1
6 2 8
1 4 5

26