Optimal Seating Assignment

During a class party, the homeroom teacher imposes a rule to facilitate management: during dinner, students from the same dorm must sit together. However, during the entertainment session after dinner, students form groups according to their game preferences. This scenario gives rise to a seating rearrangement problem.

There are \(n\) circular tables arranged in a row (numbered from \(0\) to \(n-1\) from left to right), and each table has \(m\) seats (numbered from \(0\) to \(m-1\) in counterclockwise order). At dinner, every seat is occupied. After dinner, every person chooses a new seat; the new seat for the person originally sitting at table \(i\) in seat \(j\) must be chosen from the tables numbered from \(L_{i,j}\) to \(R_{i,j}\) (inclusive). The chosen seat at the destination table can be any of the \(m\) seats. Note that the overall seating assignment is a permutation (each seat is occupied by exactly one person).

The energy cost for a person moving from their original seat to the new seat is calculated in two steps:

1. Move from the starting table (table \(i\)) to the "corresponding seat" of the destination table (table \(k\)). The cost for moving between tables is \(2\times|i-k|\).
2. On the destination table, move from the corresponding seat to the actual chosen seat. Since the table is circular, the person picks the shortest path. The cost is the circular distance given by \[ \min(|x-y|,\, m-|x-y|), \] where \(x\) is the index of the corresponding seat (which carries the same index as \(j\)) and \(y\) is the chosen seat index.

The total cost for a person originally at table \(i\), seat \(j\) who moves to table \(k\), seat \(y\) is therefore:

[ \text{Cost} = 2\times|i-k| + \min(|j-y|,, m-|j-y|). ]

Your task is to design an assignment of people to new seats (a permutation over all \(n\times m\) seats) that minimizes the total energy consumption, while ensuring that each person chooses a destination table within his/her allowed range \([L_{i,j}, R_{i,j}]\). It is guaranteed that a solution exists.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq \text{small limits}\)). Then \(n\times m\) lines follow. The \(i\)th block of \(m\) lines (\(0 \le i \le n-1\)) corresponds to table \(i\). Each of these \(m\) lines contains two integers \(L_{i,j}\) and \(R_{i,j}\) (with \(0 \leq L_{i,j} \leq R_{i,j} \leq n-1\)), representing the allowed destination table range for the student originally sitting at seat \(j\) of table \(i\).

Note: Tables and seats are 0-indexed.

outputFormat

Output a single integer, the minimum total energy consumption. In particular, the total cost is computed as the sum over all persons of

[ 2\times|i-k| + \min(|j-y|,, m-|j-y|), ]

where a person from table (i), seat (j) is assigned to table (k) and seat (y) in the new seating arrangement.

sample

1 3
0 0
0 0
0 0

0