Migrated from Lutece 2979 座位分配

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大厅里有 $n$ 张排成一排的桌子，相邻桌子的距离为 $1$，并且从左至右编号为 $0$ 到 $n-1$，每张桌子有 $m$ 个座位，座位等间距排列，按照逆时针依次编号为 $0$ 到 $m-1$，初始每个座位上都有一个人。 有的人可能对他们的座位不满意，所以现在每个人都需要改换自己的座位（可以不动），但是每个人对于自己的新座位也有一定的要求。具体来说，第 $i$ 桌第 $j$ 个人的新座位对应的桌子的编号只能在区间 $[L_{i,j},R_{i,j}]$ 中，不过座位可以是这些桌中的任何一个。确定好新座位之后，大家开始换座位，代价可按如下规则计算：

过程分为两步：

从当前座位移动到目标桌编号相同的座位，从第 $i$ 桌移动到第 $j$ 桌编号相同的座位的代价为 $2\times|i-j|$；

从当前座位移动到位于同一桌的目标座位，桌子是圆的，人们会选择最近的方向移动，从编号为 $x$ 的座位移动到编号为 $y$ 的座位的代价为 $\min(|x-y|, m-|x-y|)$；

例如，每张桌子有 $10$ 个座位，verjun 想从 $3$ 号桌的 $2$ 号座位移动到 $2$ 号桌的 $9$ 号座位，则代价为 $2\times |3-2|+\min(10-|2-9|,|2-9|)=2+3=5$。

Input

第一行输入两个整数$n, m,(1\le n\le 300,1\le m\le 10)$，代表桌子数目与每张桌子的座位数目。 接下来输入 $n$ 行，每行 $m$ 个整数，第 $i$ 行的第 $j$ 个数表示 $L_{i,j}$； 接下来输入 $n$ 行，每行 $m$ 个整数，第 $i$ 行的第 $j$ 个数表示 $R_{i,j}$。

保证数据随机生成

Output

输出所有可能的移动方案中的最小代价，如果没有则输出no solution。

Samples

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

10

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

no solution

Resources

2023 UESTC ICPC Training for Graph