按照官方题解中的方式建立坐标系。

Jerry 走到终点（右上方无穷远）的最短路（即触碰老鼠炸弹的最少数量）等于以下图 $G_0$ 的最大流：

• 所有节点由所有范围内的整点、源点 $s$ 和汇点 $t$ 组成。
• $s$ 向左上边界的所有整点连 capacity 为 $+\infty$ 的边。
• 右下边界的所有整点向 $t$ 连 capacity 为 $+\infty$ 的边。
• 每个整点 $(x,y)$ 向左 $(x-1,y)$、上 $(x,y+1)$ 连 capacity 为 $+\infty$ 的边。
• 把 Tom 放置的每个机械猫拆成单位线段，连若干条向右或下的边，capacity 为 $1$。

这由熟知的结论“最大流 = 最小割 = 对偶图最短路”保证。

上述建图方式可以优化为 $G_1$：

• 所有节点由所有机械猫经过的整点、源点 $s$ 和汇点 $t$ 组成。
• $s$ 向左上边界的所有整点连 capacity 为 $+\infty$ 的边。
• 右下边界的所有整点向 $t$ 连 capacity 为 $+\infty$ 的边。
• 每个整点 $(x_1,y_1)$ 左上方的所有整点 $(x_2,y_2)\ (x_2\le x_1,y_2\ge y_1)$ 连 capacity 为 $+\infty$ 的边（1 类边）。
• 把 Tom 放置的每个机械猫拆成单位线段，连若干条向右或下的边，capacity 为 $1$（2 类边）。

显然，$G_0,G_1$ 的最大流相同。

进一步优化到 $G_2$：

• 所有节点由所有机械猫的端点、源点 $s$ 和汇点 $t$ 组成。
• $s$ 向左上边界的所有点连 capacity 为 $+\infty$ 的边。
• 右下边界的所有点向 $t$ 连 capacity 为 $+\infty$ 的边。
• 每个点 $(x_1,y_1)$ 左上方的所有点 $(x_2,y_2)\ (x_2\le x_1,y_2\ge y_1)$ 连 capacity 为 $+\infty$ 的边（1 类边）。
• 把 Tom 放置的每个机械猫看成一条线段，连向右或下的边，capacity 为 $1$（2 类边）。

显然，$G_2$ 的每个合法流都对应 $G_1$ 的一个合法流。因此，$\operatorname{max\_flow}(G_2)\le \operatorname{max\_flow}(G_1)$。

为了证明 $\operatorname{max\_flow}(G_1)\le \operatorname{max\_flow}(G_2)$，可以把 $G_1$ 的任意一个合法流转化成 $G_2$ 中的一个流量相同的合法流。

• 对于每只机器猫，设其在 $G_1$ 中对应的边为 $v_1\to v_2\to \cdots\to v_l$，在 $G_2$ 中对应的边为 $v_1\to v_l$。
  • 对于所有 2 类边 $v_i\to v_{i+1}$，若流量为 $0$，把流量改为 $1$，并把 1 类边 $v_{i+1}\to v_i$ 的流量增加 $1$。
  • 把 $G_1$ 中的流 $v_1\to v_2\to \cdots\to v_l$ 替换为 $G_2$ 中的 $v_1\to v_l$。
• 处理 1 类边：
  • 对于一个在 $G_1$ 中，但不在 $G_2$ 中的点 $v$，在上述处理后，与 $v$ 关联的只有 1 类边。
  • 不停地把 1 类边上的流 $u\to v\to w$ 替换为 $u\to w$，因为流量平衡，这个过程结束时，所有与这样的 $v$ 关联的 $v$ 流量均为 $0$。

因此 $G_1,G_2$ 的最大流相同。

提示：考虑以下输入数据。

1
3 9 2
9 0 5 1
0 7 2 1
2 9 10 1