Problem Description

During a class party, the homeroom teacher requires that, during dinner, students from the same dormitory must sit together to make management easier. However, after dinner, during entertainment time, students who like different games will gather together. This involves the problem of seat reassignment.

There are $n$ round tables in a row (numbered from left to right as $0$ to $n-1$). Each table has $m$ seats (numbered counterclockwise as $0$ to $m-1$). During dinner, every seat is occupied by one person. After dinner, everyone must choose a new seat (which may be the same as the original one). Specifically, the person at table $i$, seat $j$ can only choose a new seat on some table between $L_{i,j}$ and $R_{i,j}$ (inclusive), and it can be any seat on any of those tables. After all new seats are decided, everyone starts moving. The physical cost is computed as follows:

The movement has two steps:

1. Move from the starting table to the corresponding seat on the target table. The cost is twice the distance between the two tables. That is, moving from table $i$ to the corresponding seat on table $j$ costs $2\times |i-j|$.
2. Move around the target table from the corresponding seat to the target seat. Since the table is round, the guest will choose the shorter direction. The cost is one times the moved distance. That is, moving from seat $x$ to seat $y$ costs $\min(|x-y|,m-|x-y|)$.

See the figure below for details:

Now, given each guest’s constraint (the interval of tables where their new seat may be), you need to design a plan to minimize the sum of physical costs of all guests. In this problem, assume guests do not affect each other while moving.

Input Format

Read from standard input.

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

Next $n$ lines follow, each containing $m$ space-separated integers describing matrix $L$. The $j$-th number in the $i$-th line is $L_{i,j}$.

Next $n$ lines follow, each containing $m$ space-separated integers describing matrix $R$. The $j$-th number in the $i$-th line is $R_{i,j}$.

The testdata is randomly generated. The pseudocode is:

for i <- 0 to n-1
    for j <- 0 to m-1
        L[i,j] <- independently and uniformly pick an integer from 0 to n-1
        R[i,j] <- independently and uniformly pick an 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

Write to standard output.

Output the minimum total physical cost. If there is no feasible plan, output no solution.

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

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

Hint

Sample Explanation

For sample $1$:

Persons $0$ and $3$ at table $0$, as well as person $0$ and $2$ at table $1$, are restricted to sit only at their original table (not necessarily their original seat). Others need to move to table $1$ and table $0$, respectively.

It can be seen that the optimal plan is as shown above, and the total physical cost is $10$.

For sample $2$, everyone wants to sit at table $0$, so there is no feasible plan.

Constraints: $1\le n\le 300$, $1\le m\le 10$, $0\le L_i\le R_i\le n-1$. | Test Point | $n\le$ | | :----------: | :----------: | | 1~2 | $2$ | | | 3~8 | $40$ | | | 9~14 | $100$ | | | 15~20 | $300$ | |

Translated by ChatGPT 5