题目描述

给出一个 $N\times 3$ 的棋盘，上面写有数字。给你 $K$ 块 $1\times 2$ 的多米诺骨牌，请你求出用这 $K$ 块骨牌能覆盖的棋盘上的数字之和的最大值。

输入格式

第一行，两个整数 $N$ 和 $K$，分别表示棋盘的行数和骨牌块数；

接下来 $N$ 行，每行 $3$ 个整数，表示棋盘上的数字。

输出格式

输出一个整数，表示这 $K$ 块骨牌能覆盖的棋盘上的数字之和的最大值。

5 3
2 1 -1
1 3 2
0 2 3
2 1 1
3 3 0 

16 

2 2
0 4 1
3 5 1 

13

提示

【样例解释 #1】

如图，总和为 $3+2+2+3+3+3=16$，可以证明这是最大的。

【数据范围】

对于 $100\%$ 的数据，$1\le N,K\le 1000$。

【说明】

本题分值按 COCI 原题设置，满分 $120$。

题目译自COCI2013_2014 CONTEST #5 T4 DOMINE