P15666 [ICPC 2025 Jakarta R] Down Right Chips

You have a board of size $N \times M$, with rows numbered from $1$ to $N$ from top to bottom, and columns numbered from $1$ to $M$ from left to right. Initially, there are $A_{i,j}$ chips on the tile at the $i$-th row and $j$-th column. You will play a solitaire game on this board. In one move, you can do one of the following. - Choose a tile not in the bottommost row with at least two chips on it. Discard one chip from the tile, and move another chip to the tile directly below it. - Choose a tile not in the rightmost column with at least one chip on it. Move one chip from the tile to the tile directly to its right. The game ends when there are no more moves you can make. There will be $Q$ changes to the board, and each of the changes will $\textbf{add}$ $W$ chips to the tile at the $X$-th row and $Y$-th column. After each change, calculate the minimum number of moves to end the game using the current board.

The first line contains three integers $N$, $M$, and $Q$ ($1 \leq N \leq 5$; $1 \leq M, Q \leq 100\;000$). The next $N$ lines, each containing $M$ integers, represent $A_{i,j}$ ($0 \leq A_{i,j} \leq 100\;000$). Each of the next $Q$ lines contains three integers $X$, $Y$, and $W$ ($1 \leq X \leq N$; $1 \leq Y \leq M$; $1 \leq W \leq 10\;000$) representing a change to the board.

Output $Q$ lines, each containing a single integer representing the minimum number of moves to end the game after each change.

$\textit{Explanation of Sample 1:}$ After the first change, you can play as follows for the minimum number of moves. - Move $\textit{right}$ on tile $(1, 2)$. - Move $\textit{down}$ on tile $(1, 2)$. - Move $\textit{right}$ on tile $(2, 2)$. - Move $\textit{right}$ on tile $(2, 2)$. - Move $\textit{down}$ on tile $(1, 3)$.