CF513F2 Scaygerboss

Cthulhu 决定去抓 Scaygerboss。Scaygerboss 得知后，正试图躲藏在一群 scayger 中。除了 Scaygerboss 之外，每只 scayger 不是雄性就是雌性。Scaygerboss 的性别为“其他”。 scayger 们分布在一个被划分为若干格子的二维地图上。如果某只 scayger 与恰好一只性别与自己不同的 scayger 处于同一个格子中，则它看起来 nerdy 且 loveable。如果地图上的所有 scayger 都看起来 nerdy 且 loveable，那么 Cthulhu 就无法抓住 Scaygerboss。 scayger 们可以以不同的速度移动。对于每只 scayger，给出了它从一个格子移动到相邻格子所需的时间。若两个格子有公共边，则它们相邻。在任意时刻，每个没有障碍物的格子可以被任意数量的 scayger 占据。scayger 不能移动到有障碍物的格子。 请计算，为了让所有 scayger 都看起来 nerdy 且 loveable，若 scayger 们以最优方式移动，所需的最短时间。

第一行包含四个整数 $n$、$m$、$males$、$females$（$0 \leq males, females \leq n \cdot m$）。$n$ 和 $m$ 表示地图的尺寸；$males$ 和 $females$ 分别表示雄性和雌性 scayger 的数量。 接下来的 $n$ 行描述地图。每行包含 $m$ 个字符。字符 '.' 表示空格子，字符 '#' 表示有障碍物的格子。 下一行包含三个整数 $r$、$c$、$t$（$1 \leq r \leq n$，$1 \leq c \leq m$，$1 \leq t \leq 10^{9}$）：分别表示 Scaygerboss 的当前位置坐标和其移动到相邻格子的时间。接下来的 $males$ 行，每行包含一只雄性 scayger 的坐标和移动时间，格式与 Scaygerboss 相同。再接下来的 $females$ 行，每行包含一只雌性 scayger 的坐标和移动时间，格式同上。（所有 scayger 均位于无障碍物的格子。） 本题包含两个子任务。子任务的输入约束不同。提交每个子任务的正确解都可以获得相应分数。子任务描述如下： - 子任务 F1（$14$ 分）：满足 $1 \leq n, m \leq 11$。 - 子任务 F2（$6$ 分）：满足 $1 \leq n, m \leq 22$。

输出使所有 scayger 看起来 nerdy 且 loveable 所需的最短时间。如果无法实现，输出 $-1$。

请参考第一个样例测试。scayger 们藏在一个 $4 \times 4$ 的地图上。Scaygerboss 最初位于格子 $(2,1)$，移动到相邻格子需要 $1$ 单位时间。还有 $2$ 只雄性和 $3$ 只雌性 scayger。其中一只雌性最初在格子 $(1,1)$，其余所有 scayger 都在格子 $(2,1)$。所有这些 scayger 移动到相邻格子都需要 $2$ 单位时间。如果 Scaygerboss 和 $(1,1)$ 的那只雌性 scayger 移动到 $(1,2)$，而 $(2,1)$ 的一只雄性和一只雌性 scayger 移动到 $(1,1)$，那么所有 scayger 都会在 $2$ 单位时间后看起来 nerdy 且 loveable。 由 ChatGPT 4.1 翻译