P15666 [ICPC 2025 Jakarta R] Down Right Chips

你有一个大小为 $N \times M$ 的棋盘，行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $M$。初始时，第 $i$ 行第 $j$ 列的格子上有 $A_{i,j}$ 个筹码。 你将在这个棋盘上玩一个单人游戏。在一次操作中，你可以执行以下两种操作之一。 - 选择一个不在最底行且至少有两个筹码的格子。丢弃该格子的一个筹码，并将另一个筹码移动到正下方的格子。 - 选择一个不在最右列且至少有一个筹码的格子。将该格子的一个筹码移动到正右方的格子。 当无法再进行任何操作时，游戏结束。 棋盘会发生 $Q$ 次变动，每次变动会**增加** $W$ 个筹码到第 $X$ 行第 $Y$ 列的格子上。在每次变动后，计算使用当前棋盘结束游戏所需的最少操作次数。

第一行包含三个整数 $N$、$M$ 和 $Q$（$1 \leq N \leq 5$；$1 \leq M, Q \leq 100\;000$）。 接下来的 $N$ 行，每行包含 $M$ 个整数，表示 $A_{i,j}$（$0 \leq A_{i,j} \leq 100\;000$）。 接下来的 $Q$ 行，每行包含三个整数 $X$、$Y$ 和 $W$（$1 \leq X \leq N$；$1 \leq Y \leq M$；$1 \leq W \leq 10\;000$），表示一次棋盘变动。

输出 $Q$ 行，每行包含一个整数，表示每次变动后结束游戏所需的最少操作次数。

**样例 1 解释：** 在第一次变动后，你可以按以下方式进行最少次数的操作。 - 在格子 $(1, 2)$ 上执行**右移**操作。 - 在格子 $(1, 2)$ 上执行**下移**操作。 - 在格子 $(2, 2)$ 上执行**右移**操作。 - 在格子 $(2, 2)$ 上执行**右移**操作。 - 在格子 $(1, 3)$ 上执行**下移**操作。 翻译由 DeepSeek V3.2 完成