给定一个大小为 $n \times (2k + 1)$ 的矩阵 $a$，其中行编号从 $1$ 到 $n$，列编号从 $-k$ 到 $k$。

你需要选择一个数列 $x_1, x_2, \dots, x_n$，使得满足约束条件 $(-k \le x_i \le k)$ 且 $(x_1 + x_2 + \dots + x_n = 0)$，并在此前提下，使 $a_{1,x_1} + a_{2,x_2} + \dots + a_{n,x_n}$ 的值尽可能小。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 35\,000, 1 \le k \le 3$)，用空格分隔，表示矩阵 $a$ 的维度。

接下来的 $n$ 行，每行包含 $(2k + 1)$ 个整数，用空格分隔：第 $i$ 行的第 $j$ 个数表示矩阵 $a$ 中第 $i$ 行第 $(j - k - 1)$ 列的元素 ($-10^9 \le a_{i,j-k-1} \le 10^9$)。

输出格式

输出一个整数：在满足约束条件 $(-k \le x_i \le k)$ 和 $(x_1 + x_2 + \dots + x_n = 0)$ 的前提下，和 $a_{1,x_1} + a_{2,x_2} + \dots + a_{n,x_n}$ 的最小值。

样例

样例输入 1

3 1
3 14 15
-3 -5 -35
2 71 82

样例输出 1

-19

样例输入 2

5 2
1 2 5 14 42
1 2 3 5 8
1 2 4 8 16
1 2 3 4 5
1 2 6 24 120

样例输出 2

16

说明

在第一个样例中，最优解是选择序列 $0, 1, -1$，这将得到所需的结果，即 $15 + (-35) + 2 = -19$。