题目描述

给定一个 $n$ 行 $3$ 列的方格图，每个方格里都有个分数，其中第 $i$ 行第 $j$ 列的分数为 $a_{i,j}$，可能存在负数。

有 $n$ 张多米诺骨牌，每张骨牌恰好可以覆盖两个相邻的方格，每张骨牌可以横放，也可以竖放。

小爱必须将所有的骨牌都放到图上去，骨牌之间不能有重叠。请问这些骨牌最多能盖住多少分数。

输入格式

第一行：单个整数 $n$。 第二行和第 $n+1$ 行：第 $i+1$ 行有三个整数，分别表示 $a_{i,1}$, $a_{i,2}$ 和 $a_{i,3}$

输出格式

单个整数：这些骨牌可以覆盖的最大分数之和。

3
1 1 1
2 2 2
3 3 3

15

样例解释 1

盖住最后两行

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

-5

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 300$；
• 对于 $60\%$ 的数据，$1\leq n\leq 2000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 5000$，$-1000000\leq a_{i,j}\leq 1000000$。