Line of Bentham

N people stand in a line facing forward. The front person is number 1 and the back person is number N.

Each person distinguishes at most the 3 people directly ahead. For person $i$ and person $j$, the integer $p_{i,j}$ records how much $i$ likes $j$ and lies from $-10$ to $10$. The happiness of person $i$ is $q_i = p_{i,i-3} + p_{i,i-2} + p_{i,i-1}$. When $j \le 0$, define $p_{i,j} = 0$. The total happiness is $Q = \sum_{i=1}^{N} q_i$.

Any positions in the line may be replaced with dispatched agents. An agent has happiness $0$ and does not affect the happiness of people behind. There is no limit on the number of agents.

Compute the maximum total happiness obtainable from the N people.

The first line gives the number of people $N$ with $3 \le N \le 1,000,000$.

The next $N$ lines describe each person. The line for person $i$ gives three integers $p_{i,i-3}$, $p_{i,i-2}$ and $p_{i,i-1}$.

When $j \le 0$, the value $p_{i,j}$ is given as $0$. All other $p_{i,j}$ are integers from $-10$ to $10$.

Print the maximum total happiness obtainable after replacing some people with agents.

In the public sample input, keeping everyone gives happiness values $0$, $2$, $-3$ and $1$ for a total of $0$. Replacing persons $1$ and $2$ with agents gives $0 + 0 + 0 + 2 = 2$, and no replacement reaches a larger total.