Mirko 有一个 $N$ 行 $3$ 列的棋盘。Slavica 在棋盘的每个格子上都写了一个整数。Mirko 手头有 $K$ 个大小为 $2 \times 1$ 的骨牌，他需要将它们全部摆放在棋盘上，且任意两个骨牌不能重叠。每个骨牌必须恰好覆盖棋盘上的两个相邻格子。他可以任意旋转骨牌。

请帮助 Mirko 摆放骨牌，使得被骨牌覆盖的格子上的数字之和最大！

输入格式

输入的第一行包含两个整数 $N$ ($1 \le N \le 1000$)，表示棋盘的行数，以及 $K$ ($1 \le K \le 1000$)，表示可用的骨牌数量。

接下来的 $N$ 行，每行包含三个整数，表示棋盘第 $i$ 行的三个格子上的数字。所有数字的绝对值都小于 $10^6$。

输出格式

输出仅一行，包含一个整数，表示用恰好 $K$ 个骨牌所能覆盖的最大数字之和。

样例

输入样例 1

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

输出样例 1

16

输入样例 2

2 2
0 4 1
3 5 1

输出样例 2

13

说明

样例 1 说明：最优策略是水平放置所有骨牌，分别覆盖第二行的右侧两个格子（第 2、3 列）、第三行的右侧两个格子（第 2、3 列）以及最后一行的左侧两个格子（第 1、2 列）。