Problem Description

During a class reunion, the homeroom teacher sets a rule for convenience management: students from the same dormitory must sit together during meals. However, after the meal, students who enjoy different games gather together, which involves the issue of seat allocation.

There are $n$ round tables arranged in a row (numbered from $0$ to $n-1$ from left to right), each with $m$ seats (numbered counterclockwise from $0$ to $m-1$). During the meal, each seat is occupied by someone. After the meal, everyone needs to choose a new seat (which may be the same as the original seat). Specifically, the new seat for the person at the $i$-th table and $j$-th seat can only be chosen from the $L_{i,j}$-th table to the $R_{i,j}$-th table, including any seat at these tables. After deciding on the new seat, people start moving. The physical exertion for moving is calculated as follows:

The process of moving seats consists of two steps:

1. Moving from the starting table to the target table's corresponding seat. The physical exertion for this step is twice the distance between the two tables, i.e., moving from the $i$-th table to the $j$-th table's corresponding seat consumes $2 \times |i-j|$ physical exertion.
2. Moving from the target table's corresponding seat to the target seat. Since the tables are round, guests will choose the shortest direction to move, consuming physical exertion equal to the distance moved, i.e., moving from seat number $x$ to seat number $y$ consumes $\min(|x-y|, m-|x-y|)$ physical exertion.

See the diagram below for details:

Given the restrictions for each guest (i.e., the interval where their new seat can be), you need to design a plan that minimizes the total physical exertion of all guests. Assume that guests do not affect each other during the move.

Input Format

Input is read from standard input.

The first line contains two numbers $n$ and $m$.

The next $n$ lines, each containing $m$ space-separated integers, describe matrix $L$: the $j$-th number in the $i$-th line represents $L_{i,j}$.

The following $n$ lines, each containing $m$ space-separated integers, describe matrix $R$: the $j$-th number in the $i$-th line represents $R_{i,j}$.

The data is randomly generated with the following pseudocode:

for i <- 0 to n-1
    for j <- 0 to m-1
        L[i,j] <- independently and equally likely to be any integer from 0 to n-1
        R[i,j] <- independently and equally likely to be any integer from 0 to n-1
        if L[i,j] > R[i,j] then
            tmp <- L[i,j]
            L[i,j] <- R[i,j]
            R[i,j] <- tmp

Output Format

Output is written to standard output.

Output the minimum total physical exertion. If there is no valid solution, output no solution.

Sample Input and Output

Input Sample #1

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

Output Sample #1

10

Input Sample #2

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

Output Sample #2

no solution

Input Sample #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

Output Sample #3

22

Notes/Hints

Sample Explanation

For Sample 1,

The $0$-th and $3$-th at the $0$-th table, and the $0$-th and $2$-th at the $1$-th table are restricted to sit at their original tables (not necessarily the same seats), while others need to switch to the $1$-th and $0$-th tables respectively.

It can be found that the optimal solution, as shown in the diagram, results in a total physical exertion of $10$.

For Sample 2, everyone wants to sit at the $0$-th table, so there is no valid solution.

For all data: $1 \le n \le 300$, $1 \le m \le 10$, $0 \le L_i \le R_i \le n-1$.

见题面 Input 部分

见题面 Output 部分