Description

The leader has a circular garden and wants to plant $n$ trees evenly around it. However, the soil is special; each position suits different kinds of trees, and some trees may lose aesthetic value if placed in unsuitable soil.

The leader's three favorite kinds of trees have heights $10,20,30$. He wants the ring of trees to have a sense of layering: at every position, the tree must be strictly higher than both of its adjacent trees or strictly lower than both. Under this condition, design a plan that maximizes the sum of aesthetic values.

Input Format

The first line contains a positive integer $n$, the number of trees to plant.

The next $n$ lines each contain three positive integers $a_i,b_i,c_i$ not exceeding $10000$, giving, in clockwise order, the aesthetic value obtained by planting at position $i$ a tree of height $10,20,30$, respectively.

The tree at position $i$ is adjacent to the tree at position $i+1$; in particular, the tree at position $1$ is adjacent to the tree at position $n$.

Output Format

Output a single positive integer, the maximum total aesthetic value.

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

11

Hint

[Sample Explanation].

Plant trees of heights $20,10,30,10$ at positions $1$ through $n$, respectively, to achieve the highest value.

[Constraints].

• For $20\%$ of the testdata, $n \le 10$.
• For $40\%$ of the testdata, $n \le 100$.
• For $60\%$ of the testdata, $n \le 1000$.
• For $100\%$ of the testdata, $4 \le n \le 10^5$, and $n$ is guaranteed to be even.

Translated by ChatGPT 5