多米诺骨牌(Dominoes)

题目描述

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

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

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

输入格式

第一行：单个整数 $n$。

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

输出格式

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

样例输入 #1

3
1 1 1
2 2 2
3 3 3

样例输出 #1

15

样例说明

盖住最后两行。

样例输入 #2

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

样例输出 #2

-5

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 6级（动态规划、状态压缩），难度等级：⭐⭐⭐⭐⭐。