题目描述

班级聚会时，有 $n$ 张圆桌排成一排（编号 $0$ 到 $n-1$），每张桌子有 $m$ 个座位（逆时针编号 $0$ 到 $m-1$）。吃饭时每个座位都有人，娱乐时间每个人需选择新座位，且第 $i$ 桌第 $j$ 个人的新座位必须在第 $L_{i,j}$ 桌到 $R_{i,j}$ 桌之间（可任选这些桌的任意座位）。

移动的体力消耗分两步计算：

1. 桌间移动：从第 $i$ 桌到第 $j$ 桌对应座位，消耗为 $2 \times |i-j|$；
2. 桌内移动：从目标桌的对应座位到最终座位，消耗为 $\min(|x-y|, m-|x-y|)$（选择最近方向）。

详情如下图：

需设计方案使所有人的体力消耗总和最小，若无合法方案输出 no solution。

输入格式

从标准输入读入数据：

• 第一行输入两个整数 $n$ 和 $m$；
• 接下来 $n$ 行，每行 $m$ 个整数描述矩阵 $L$，第 $i$ 行第 $j$ 个数为 $L_{i,j}$；
• 接下来 $n$ 行，每行 $m$ 个整数描述矩阵 $R$，第 $i$ 行第 $j$ 个数为 $R_{i,j}$。

数据随机生成规则：

for i <- 0 to n-1
    for j <- 0 to m-1
        L[i,j] <- 独立等概率地得到 0 到 n-1 中的一个整数
        R[i,j] <- 独立等概率地得到 0 到 n-1 中的一个整数
        if L[i,j] > R[i,j] then
            tmp <- L[i,j]
            L[i,j] <- R[i,j]
            R[i,j] <- tmp

输出格式

输出到标准输出：

• 若有合法方案，输出总体力消耗的最小值；
• 若无合法方案，输出 no solution。

样例 1

样例输入

2 4
0 1 1 0
1 0 1 0
0 1 1 0
1 0 1 0

样例输出

10

样例说明

第 $0$ 桌的 $0$ 和 $3$ 号、第 $1$ 桌的 $0$ 号和 $2$ 号只能坐原桌，其他人需换桌，最优方案总体力消耗为 $10$。

样例 2

样例输入

2 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

样例输出

no solution

样例说明

所有人都想坐到第 $0$ 桌，无合法分配方案。

样例 3

样例输入

2 10
0 0 1 1 0 0 0 1 0 0
1 1 1 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 0

样例输出

22

样例说明

详见附加文件。

数据范围与提示

测试点	$n$ 的限制	$m$ 的限制
1, 2	$1 \le n \le 2$	$1 \le m \le 10$
3-8	$1 \le n \le 40$
9-14	$1 \le n \le 100$
15-20	$1 \le n \le 300$