Let us allow multiple pieces to occupy the same cell during the operations. If each cell has at most one piece in the final state, this relaxation does not change the answer.

Let us first find \(f(1,N)\) for the case where \(M\) is even.

Let \(r_1,r_2,\ldots,r_k\) be the rows that initially have an odd number of pieces. If \(k\) is odd, it is impossible to make the number of pieces in every row even, so \(f(1,N)=0\).

Let us consider the case where \(k\) is even. As a lower bound for \(f(1,N)\), we can consider the value \((r_2-r_1)+(r_4-r_3)+\cdots+(r_{k}-r_{k-1})\). However, there are cases where this is not sufficient. An example is the following:

O...  (r_1)
O..O
O.O.
O...  (r_2)

In this example, three operations are not enough, and four operations are needed. In general, when the following conditions hold between a pair of odd rows \((l,r)\), the minimum cost of pairing \(l,r\) is \(r-l+1\).

• \(S_l=S_r\)
• For every \(l<i<r\), \(S_l\) and \(S_i\) differ in exactly one column.

The proof can be done by induction.

Below, let \(cost(l,r)\) denote the cost of pairing odd rows \(l,r\). Then, we can compute \(f(1,N)=\sum_{i=1,3,\ldots,k-1} cost(r_i,r_{i+1})\). That is, pairing the odd rows in order is an optimal solution itself.

This can be proved with the following approach. For example, suppose we have four odd rows \(a<b<c<d\). If we pair them in order as \((a,b),(c,d)\), the cost is at most \((b-a)+(d-c)+2\). On the other hand, if we consider a solution that does not pair them in order, the cost requires at least \((c-a)+(d-b)\), which is at least \((b-a)+(d-c)+2\). Thus, we see that there is no disadvantage to pairing them in order. This kind of argument can be carried out in general, showing that the structure of an optimal solution is to pair the odd rows in order.

Once we know this structure, computing \(\sum f(L,R)\) is also easy. We consider the two possible parities of the number of odd rows before row \(L\), and for each pattern, we can independently compute the contribution of each odd-row pair. The time complexity is \(O(NM)\).

Next, let us consider the case where \(M\) is odd. Let us first find \(f(1,N)\).

First, consider the case where there is no row with \(M\) pieces placed. Then, we see that this can be solved in exactly the same way as when \(M\) is even.

Now, what should we do when there is a row with \(M\) pieces placed? First, it is fine to restrict ourselves to solutions with the following structure.

• Step 1: As long as there exists a row with \(M\) pieces placed, choose a piece in such a row and operate on it.
• Step 2: Once there are no more rows with \(M\) pieces placed, the optimal procedure can be computed, so follow it.

Here, let \(c_i\) be the number of pieces placed in row \(i\) in the initial state, and \(d_i\) be the number of pieces placed in row \(i\) after Step 1 of an optimal solution finishes.

Here, the following properties can be confirmed for \(c_i\), \(d_i\).

• If \(c_i=M\), then \(d_i=M-1\).
• If \(c_i \leq M-1\), then \(c_i \leq d_i \leq M-1\).
• Consider the value \(e_i=c_i-d_i\). Consider matching the positive parts of \(e_i\) with the negative parts of \(e_i\) in order. For example, if \(e=(+1,0,-2,+1)\), then match \(1 \to 3\), \(4 \to 3\). (Written in the order positive side \(\to\) negative side)
• If there is a match \(u \to v\) (\(u<v\)), then \(d_u,d_{u+1},\ldots,d_{v-1}\) are all \(M-1\).
• If there is a match \(u \to v\) (\(u>v\)), then \(d_u,d_{u-1},\ldots,d_{v+1}\) are all \(M-1\).

Now, given \(d_i\), let us consider finding the minimum number of moves corresponding to it. First, minimizing the number of row moves is easy. After matching the positive and negative parts of \(e_i\) in order, we should again match the odd rows of \(d_i\) in order. What is the number of column moves in this case? First, for each pair of odd rows \(l,r\) in \(d_i\) satisfying the following conditions, one additional column move is needed.

• The row moves due to the matching of \(e_i\) do not involve the interval \([l,r]\) (including endpoints) at all.
• \(S_l=S_r\).
• For every \(l<i<r\), \(S_i\) and \(S_l\) differ in exactly one column.

Conversely, for any other odd pair, the additional column moves can be kept at zero. Let us confirm this dutifully. First, if a move between rows \(z,z+1\) occurs due to the matching of \(e_i\), we say that rows \(z,z+1\) are connected.

Let us focus on a connected component. Suppose this connected component is a row interval \([L,R]\). Within this connected component, the matches \(u\to v\) are either all in the direction \(u<v\), or all in the direction \(u>v\). Let us consider the case \(u<v\) (the case \(u>v\) is similar).

Here, when performing the operation \(u \to v\), all \(M\) columns are filled in row \(u\), so we can choose to move to any column we like among row \(v\)’s empty cells. Here, if \(R\) itself is an odd row, then the state of row \(R\) can be chosen from two or more options, so the column move related to row \(R\) can be avoided.

Now, what about the case where \(R\) is an even row sandwiched between other odd rows? Actually, this case does not occur. This is because, if \(R\) is an even row sandwiched between other odd rows, we can remove the last match \(u \to R\) of the \([L,R]\) component and pair them again as \((p,u),(R,q)\) with the odd rows \(p,q\) sandwiching \([L,R]\), obtaining a better solution. This contradicts the premise that \(d_i\) was taken from an optimal solution.

Organizing the observations so far, we see that an optimal solution can be obtained by the following procedure.

• Pair each odd row in order.
• Letting \(c'_i\) be the largest even number at most \(c_i\), row \(i\) has room to accept \((M-1-c'_i)/2\) pairs.
• Move pairs to rows that have room.
• An additional column move cost of \(+1\) is incurred only if an odd-row pair \((l,r)\) satisfies all of the following conditions.
  • Pair \((l,r)\) is absorbed by rows inside it.
  • No pair comes into \([l,r]\) from outside.
  • Looking only at \([l,r]\), the \(l,r\) pair requires a column move.

Based on this consideration, we reduce the problem to the following matching problem on a line.

• For each row \(i\), consider that there are \((m-1-c'_i)/2\) holes at coordinate \(i\).
• Let the odd rows in order be \(l_1,r_1,l_2,r_2,\ldots\). For each \((l_i,r_i)\), first add \(r_i-l_i\) to the answer. Then, place a ball at a free coordinate within the interval \([l_i,r_i]\).
• Move the balls into the holes. Each hole receives at most one ball. Letting \(X\) be the total distance moved by the balls, add \(2X\) to the answer.
• We call \((l_i,r_i)\) a bad pair when a hole exists within \([l_i,r_i]\) (that is, when looking only at rows \(l_i\) through \(r_i\), the odd rows can be eliminated), and eliminating the odd rows within it costs \(r_i-l_i+1\) (that is, rows \(l_i,r_i\) are equal, and the rows between them each differ by exactly one column).
• For each bad pair \((l_i,r_i)\), if a ball not originating from \((l_i,r_i)\) comes into a hole within \([l_i,r_i]\), we can avoid the extra column move originating from the bad pair. Conversely, if no ball comes into a hole within \([l_i,r_i]\) from outside (and the ball of \((l_i,r_i)\) itself is consumed within \([l_i,r_i]\)), an additional cost of \(1\) is incurred.

Here, when minimizing the final answer, we can prove that we may first minimize \(X\) by an argument similar to before.

Next, among the assignments that minimize \(X\), let us consider how to further minimize the cost originating from bad pairs.

To make things clearer, let us further transform the problem into the following form.

• Assign to each ball and hole not a coordinate, but an interval of coordinates.
• For a pair \((l_i,r_i)\), if no hole exists within \([l_i,r_i]\), prepare a ball assigned \([l_i,r_i]\).
• For a pair \((l_i,r_i)\), if holes exist within \([l_i,r_i]\), let the coordinates of the holes be \(x_i\) (\(l_i \leq x_1 \leq x_2 \leq \cdots \leq x_k \leq r_i\)). Then, prepare a ball assigned \([l_i,l_i]\) and a ball assigned \([r_i,r_i]\). Additionally, prepare holes assigned \([l_i,x_1], [x_1,x_2],\ldots,[x_k,r_i]\).
• To a hole in a row \(i\) not sandwiched between an odd-row pair, assign \([i,i]\).

We see that the intervals obtained in this way do not intersect each other. That is, for any two intervals \([a,b],[c,d]\), either \(b \leq c\) or \(d \leq a\) holds. Let us consider the matching problem between the holes and balls obtained in this way. The cost of matching two intervals is the distance between the intervals. Considering the minimum cost of matching all balls, we see that this equals the minimum matching in the original problem. Also, the handling of bad pairs can be written in this form: if a certain consecutive set of holes is not used at all, a penalty cost of \(+1\) is incurred.

Let us give an example. Consider the following input.

O..
OO.
...
O..
OOO
OO.
OOO
OOO
...
OOO

For this, the following balls and holes are generated.

Ball [1,1], hole [1,1], hole [1,3], hole [3,4], hole [4,4], ball [4,4], ball [5,7], ball [8,8], hole [8,9], hole [9,10], ball [10,10]

The bad-pair-originating cost \(+1\) occurs only if both hole \([1,3]\) and hole \([3,4]\) are unused.

Now let us consider how to find \(X\) concretely. Sort the holes and balls by coordinate (the order is naturally determined since the intervals do not intersect). Assign \(+1\) to holes and \(-1\) to balls, and consider the cumulative sum as a height.

We may consider that an optimal solution matches holes and balls of the same height.

Using the above example, we get the following.

                            +[4,4] -[4,4]
                     +[3,4]               -[5,7]               +[9,10] -[10,10]
              +[1,3]                             -[8,8] +[8,9]
-[1,1] +[1,1]

First, let us consider the optimal matching independently for each height. Focusing on a certain height, let us look at the number of \(-\)’s and the number of \(+\)’s. If there are more \(-\)’s, no solution exists in the first place. If the numbers are equal, the matching is uniquely determined. If there are more \(+\)’s, exactly one \(+\) must be discarded, so we can try all of them and compute the minimum cost.

How should we compute the cost of bad pairs? First, when finding the minimum cost for each height, we obtain the \(+\) intervals that could potentially be left unused. Let us call these \(+\) intervals deletion-candidate intervals.

Each bad pair corresponds to several \(+\) intervals. The case where all of these intervals are deletion-candidate intervals is important. If just one interval among them is not deleted, the cost increase can be avoided. So, in what situation is the cost increase unavoidable?

Let us call a sequence of bad pairs \(b_1,b_2,\ldots,b_k\) a bad pair chain when it satisfies the following conditions.

• Let the \(+\) intervals corresponding to \(b_i\) be \(c_{i,1},c_{i,2},\ldots,c_{i,s_i}\).
• There is no \(+\) interval \(d\) at the same height as \(c_{i,1}\) and to its left, whose deletion cost is at most that of \(c_{i,1}\).
• \(c_{i,s_i}\) and \(c_{i+1,1}\) have equal deletion costs. Also, there is no interval \(d\) at the same height between them whose deletion cost is at most that of \(c_{i,s_i},c_{i+1,1}\).
• There is no \(+\) interval \(d\) at the same height as \(c_{k,s_k}\) and to its right, whose deletion cost is at most that of \(c_{k,s_k}\).

For each such bad pair chain, the cost increases by \(1\). It is clear that accepting a cost of \(+1\) at one pair can avoid the cost increase at the other pairs. What needs to be argued is that a cost of \(+1\) cannot be avoided for each chain. More specifically, we need to confirm the following fact.

• Let \(H_L\) be the height of \(c_{i,1}\), and \(H_R\) be the height of \(c_{k,s_k}\). Collecting all deletion-candidate intervals with height between \(H_L\) and \(H_R\), inclusive, gives exactly the set \(c_{i,j}\)’s.

This can be proved as follows. First, the following property holds for deletion-candidate intervals.

• Letting \(p\) be the rightmost deletion-candidate interval at height \(h\), and \(q\) be the leftmost deletion-candidate interval at height \(h+1\), \(p\) is always to the left of \(q\).

This asserts that deletion-candidate intervals shift monotonically to the right as height increases. This can be shown either by carefully breaking down the cost formula at each stage, or by considering the structure of a globally optimal solution.

Using this property, we see that all \(c_{i,j}\)’s in a bad pair chain are deletion-candidate intervals, and there are no other deletion-candidate intervals.

With the discussion so far, computing \(f(1,N)\) is easy. Computing \(f(L,R)\) is also not difficult. We can decompose it as follows.

• Contribution from heights where the number of \(+\)’s and \(-\)’s are equal: the condition for a certain \(+,-\) pair to be usable can be written as a condition on the relative position between the point corresponding to \(L\) and the point corresponding to \(R\). This can be computed in a total of \(O(N \log N)\) time by processing it with plane sweep + a segment tree.

• Contribution to \(X\) from heights where the number of \(+\)’s and \(-\)’s are equal: considering two \(+\) intervals \(p\) and \(q\), the difference in their deletion costs is determined only by the intervals between \(p\) and \(q\). Writing this as a formula, once \(L\) and \(R\) are fixed, the \(+\) interval to be deleted can eventually be found by computing the range argmin of a certain sequence. Thus, by using a Cartesian tree, we can compute the total cost over all \(L,R\). The overall complexity is \(O(N)\).

• Contribution originating from bad pairs: the number of bad pair chains can be found with a DP. Since the conditions can be decomposed into a starting point, adjacent pairs, and an ending point, this can be done with a straightforward DP. The computation runs in \(O(N)\) time overall.

Implementing all of the above yields a solution running in \(O(NM+N \log N)\) time overall.

Sample Solution (C++)