P1133 The Leader's Garden

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.

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 a single positive integer, the maximum total aesthetic value.

[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