SP8326 LEAKCONT - Leaky containers

酸液制造公司有一个专门的房间用来存放会泄漏的酸液容器。房间中的容器支架按照 $R$ 行 $C$ 列的矩形网格排列，列的方向为南北向，行的方向为东西向。目前已有 $N$ 个容器放置在某些支架中，还有 $M$ 个新到达的容器需要放置。 公司发现这些容器最近非常容易泄漏，导致酸液腐蚀掉整个支架。 每个酸液容器的泄漏要么沿南北方向，要么沿东西方向。我们可以将容器旋转 90 度，由此改变其泄漏方向。一个泄漏的容器在足够时间内会完全腐蚀掉所在的支架，并开始腐蚀其泄漏方向上的相邻两个支架，这个过程会持续下去。 公司员工必须快速做出决定。他需要调整现有容器的方向，并为新容器找到合适的位置和方向，使得最终腐蚀的支架数量最少。 请计算经过合理放置和调整容器方向后，最少会有多少个支架被腐蚀。

输入的第一行是测试用例的数量 $T$（$T \leq 10$）。 对于每个测试用例，第一行包含四个整数 $R$、$C$、$N$ 和 $M$（$1 \leq R, C \leq 100$，$1 \leq M, N \leq 20$，$M + N \leq R \times C$）。接下来有 $N$ 行，每行描述一个现有容器的位置和其泄漏方向，格式为三个整数 $r$（行号）、$c$（列号）和 $d$（泄漏方向，1 表示南北方向，0 表示东西方向）。行号和列号从 1 开始。

对于每个测试用例，输出一行，表示通过最佳放置和调整后，最少被腐蚀的支架数量。 **本翻译由 AI 自动生成**