Let the rows where doors exist, in increasing order, be \(A'_1, \cdots, A'_{|A'|}\), and let the column numbers of doors in row \(A'_i\), in increasing order, be \(B'_{i,\ 1}, \cdots, B'_{i,\ |B'_i|}\).

The answer is the smaller of the following two cases.

Case: the elevator in column \(W\) is not used

The minimum cost is the sum, over all rows, of twice the distance (for the round trip) from column \(1\) to the farthest door.

That is, the answer is \(\displaystyle \sum_{i=1}^{|A'|} 2 (B'_{i,\ |B'_i|} - 1)\).

Case: the elevator in column \(W\) is used

The movement in row \(A'_i\) may be assumed to be one of the following three types:

• Move from column \(1\) to column \(W\).
• Move from column \(W\) to column \(1\).
• Go from column \(1\) to column \(B'_{i,\ j+0}\) and return to column \(1\), and go from column \(W\) to column \(B'_{i,\ j+1}\) and return to column \(W\) (\(0 \leq j \leq |B'_i|\)).

In the movement of type \(3\), we use sentinels \(B'_{i,\ 0} = 1\) and \(B'_{i,\ |B'_i|+1} = W\).

The movement “move from column \(1\) to column \(W\), and move from column \(W\) to column \(1\)” is also possible, but forbidding it does not worsen the optimal solution.

The costs of movements of types \(1\) and \(2\) are both \(W-1\), and the minimum cost of a movement of type \(3\) is \(\displaystyle \min_{j} \left( 2(W-1) - 2(B'_{i,\ j+1} - B'_{i,\ j+0}) \right)\).

As a global constraint on movements, movements of types \(1\) and \(2\) must be performed the same positive number of times, and conversely, if this is satisfied, a valid sequence of movements can be constructed. Since the costs of movements of types \(1\) and \(2\) are equal, the movement constraint can be rephrased as follows:

• There are \(|A'|\) integers, where the \(i\)-th is \(a_i\). When replacing a positive even number of them with \(W-1\), what is the minimum total sum?

Here, \(a_i\) is the minimum cost of a type-\(3\) movement: \(a_i := \displaystyle \min_{j} \left( 2(W-1) - 2(B'_{i,\ j+1} - B'_{i,\ j+0}) \right)\).

The rephrased problem can be solved at around ABC-C difficulty using sorting and a loop. The answer to this problem is directly the answer to the original problem.

Proposed by: sheyasutaka