题目描述

在一个有障碍的网格图中，有 male 个男人和 female 个女人，还有一个叫 BOSS 的人妖（既可以当男人又可以当女人）。这些人分布在地图上，每一个 cell（房间）可以同时有多个人。这些人每个人移动各需要 \(t_i\) 的时间，问最小需要多长时间，使得每一个人都可以和异性单独待在同一个房间里？

输入格式

在 n \(\times\) m的地图上，'.' 表示一个 free room ，既可以移动到或者经过的房间；'#' 表示一个障碍物单位，既不可达也不可经过。
第一行为四个整数，n, m, male, female，分别表示地图的行数，列数，男性和女性的个数。
接下来 n 行描述一个地图，表示是否可达。
接下来 1 行描述 BOSS（人妖），x, y, t，表示这个人所在的坐标和移动一个单位所需的时间。
接下来的 male 行和 female 行分别描述男人和女人所在的坐标和移动一个单元格所需时间，格式同上。

输出格式

输出最小时间，使得每个人都可以和异性单独呆在同一个房间里（同一个房间只能有一对人），如果不行，输出 -1。

样例1

输入

4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2

输出

2

样例2

输入

2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2

输出

-1

数据范围

对于 50%的数据，1 \(\leq\) n, m \(\leq\) 11, 0 \(\leq\) males, females \(\leq\) n \(\times\) m, 1 \(\leq\) r \(\leq\) n, 1 \(\leq\) c \(\leq\) m, 1 \(\leq\) t \(\leq\) \(10^9\)；
对于 100%的数据，1 \(\leq\) n, m \(\leq\) 22, 0 \(\leq\) males, females \(\leq\) n \(\times\) m, 1 \(\leq\) r \(\leq\) n, 1 \(\leq\) c \(\leq\) m, 1 \(\leq\) t \(\leq\) \(10^9\)。

限制

3s

样例解释

样例 1：BOSS的位置在(2, 1)，移动到相邻 cell 时间为 1，一女的位置在 (1, 1)，移动时间 2，其他 2 男 2 女的位置在(2, 1)，移动时间 2。让 BOSS 和一女从 (1, 1) 移动到 (1, 2)，所需时间为 2，让一男一女从 (2, 1) 移动 (1, 1)，所需时间为 2，最后一对男女不需要移动。

来源

Codeforces513F2
CWOI新高二专题测试十四