Cthulhu decided to catch Scaygerboss. Scaygerboss found it out and is trying to hide in a pack of his scaygers. Each scayger except Scaygerboss is either a male or a female. Scaygerboss’s gender is “other”.
Scaygers are scattered on a two-dimensional map divided into cells. A scayger looks nerdy and loveable if it is staying in the same cell with exactly one scayger of a gender that is different from its own gender. Cthulhu will not be able to catch Scaygerboss if all the scaygers on the map look nerdy and loveable.
The scaygers can move around at different speeds. For each scayger, we are given the time it takes this scayger to move from a cell to an adjacent cell. Cells are adjacent if they share a common side. At any point of time, each cell that does not contain an obstacle can be occupied by an arbitrary number of scaygers. Scaygers cannot move to cells with obstacles.
Calculate minimal time in order to make all scaygers look nerdy and loveable if they move optimally toward this goal.
Input
The first line contains 4 integers: n, m, males, females (0 ≤ males, females ≤ n·m). n and m are dimensions of the map; males and females are numbers of male scaygers and female scaygers.
Next n lines describe the map. Each of these lines contains m characters. Character ‘.’ stands for a free cell; character ‘#’ stands for a cell with an obstacle.
The next line contains 3 integers r, c, and t (1 ≤ r ≤ n, 1 ≤ c ≤ m, 1 ≤ t ≤ 109): the current coordinates of Scaygerboss and the time it takes Scaygerboss to move to an adjacent cell. The next males lines contain coordinates and times of male scaygers in the same format as for Scaygerboss. The next females lines contain coordinates and times of female scaygers in the same format as for Scaygerboss. (The coordinates and times adhere to the same limits as for Scaygerboss.) All scaygers reside in cells without obstacles.
The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.
- In subproblem F1 (14 points), the constraints 1 ≤ n, m ≤ 11 will hold.
- In subproblem F2 (6 points), the constraints 1 ≤ n, m ≤ 22 will hold.
Output
Output the minimum possible time it takes to make all scaygers look nerdy and loveable or -1 if it is impossible.
Examples
input
4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2
output
2
input
2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
output
-1
Note
Consider the first sample test. The scaygers are hiding on a 4 by 4 map. Scaygerboss initially resides in the cell (2, 1) and can move between cells in 1 unit of time. There are also 2 male and 3 female scaygers on the map. One of the females initially is in the cell (1, 1), and all the other scaygers are in the cell (2, 1). All the scaygers move between cells in 2 units of time. If Scaygerboss and the female scayger from the cell (1, 1) move to the cell (1, 2), and a male and a female scayger from those residing in the cell (2, 1) move to the cell (1, 1), then all the scaygers will look nerdy and lovable in 2 units of time.
Solution:
#include <cstring>
#include <vector>
#include <list>
#include
<map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
using namespace std;
const int inf = (int)1e9;
const int N = 1000010;
int fin;
int ss[N], ff[N], c[N], f[N], obr[N], pred[N], last[N], st[N];
int m;
void add(int x, int y, int z, int xx, int yy) {
m++;
ss[m] = x;
ff[m] = y;
c[m] = z;
f[m] = xx;
obr[m] = yy;
}
int x[N], d[N];
bool expath() {
for (int i = 0; i <= fin; i++) d[i] = -1;
int b = 1, e = 1;
x[1] = 0;
d[0] = 0;
while (b <= e) {
int j = last[x[b]];
while (j > 0) {
if (c[j] > f[j] && d[ff[j]] == -1) {
e++;
x[e] = ff[j];
d[x[e]] = d[x[b]] + 1;
if (x[e] == fin) {
return true;
}
}
j = pred[j];
}
b++;
}
return false;
}
int rec(int v, int w) {
if (v == fin) {
return w;
}
int r = 0, j = last[v];
while (j > 0) {
last[v] = pred[j];
if (c[j] > f[j] && d[ff[j]] == d[v] + 1) {
int ww = c[j] - f[j];
if (w - r < ww) ww = w - r;
int t = rec(ff[j], ww);
if (t > 0) {
f[j] += t;
if (obr[j] != 0) f[obr[j]] -= t;
r += t;
if (r == w) break;
}
}
j = pred[j];
}
return r;
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int h, w, males, females;
int mx[N], my[N], mspeed[N];
int fx[N], fy[N], fspeed[N];
int dist[42][42][42][42];
bool can(long long value) {
fin = males + 2 * h * w + females + 1;
m = 0;
for (int i = 1; i <= males; i++) {
add(0, i, 1, 0, 0);
}
for (int i = 1; i <= females; i++) {
add(males + 2 * h * w + i, fin, 1, 0, 0);
}
for (int i = 1; i <= h * w; i++) {
add(males + i, males + i + h * w, 1, 0, m + 2);
add(males + i + h * w, males + i, 0, 0, m);
}
for (int i = 1; i <= males; i++) {
for (int j = 1; j <= h * w; j++) {
int xa = mx[i - 1] - 1;
int ya = my[i - 1] - 1;
int xb = (j - 1) / w;
int yb = (j - 1) % w;
if (dist[xa][ya][xb][yb] != -1) {
if (dist[xa][ya][xb][yb] * 1LL * mspeed[i - 1] <= value) {
add(i, males + j, 1, 0, m + 2);
add(males + j, i, 0, 0, m);
}
}
}
}
for (int i = 1; i <= females; i++) {
for (int j = 1; j <= h * w; j++) {
int xa = fx[i - 1] - 1;
int ya = fy[i - 1] - 1;
int xb = (j - 1) / w;
int yb = (j - 1) % w;
if (dist[xa][ya][xb][yb] != -1) {
if (dist[xa][ya][xb][yb] * 1LL * fspeed[i - 1] <= value) {
add(males + h * w + j, males + 2 * h * w + i, 1, 0, m + 2);
add(males + 2 * h * w + i, males + h * w + j, 0, 0, m);
}
}
}
}
for (int i = 0; i <= fin; i++) {
last[i] = 0;
}
for (int i = 1; i <= m; i++) {
pred[i] = last[ss[i]];
last[ss[i]] = i;
}
for (int i = 0; i <= fin; i++) {
st[i] = last[i];
}
int ans = 0;
while (expath()) {
int t = rec(0, inf);
ans += t;
for (int i = 0; i <= fin; i++) {
last[i] = st[i];
}
}
return (ans == males);
}
char grid[42][42];
int y[N];
int main() {
scanf("%d %d %d %d", &h, &w, &males, &females);
if (abs(males - females) != 1) {
printf("%d\n", -1);
return 0;
}
for (int i = 0; i < h; i++) {
scanf("%s", grid[i]);
}
for (int ii = 0; ii < h; ii++) {
for (int jj = 0; jj < w; jj++) {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
dist[ii][jj][i][j] = -1;
}
}
if (grid[ii][jj] == '#') {
continue;
}
int b = 0, e = 0;
x[0] = ii;
y[0] = jj;
dist[ii][jj][ii][jj] = 0;
while (b <= e) {
for (int q = 0; q < 4; q++) {
int xk = x[b] + dx[q];
int yk = y[b] + dy[q];
if (xk >= 0 && yk >= 0 && xk < h && yk < w) {
if (grid[xk][yk] == '.' && dist[ii][jj][xk][yk] == -1) {
e++;
x[e] = xk;
y[e] = yk;
dist[ii][jj][xk][yk] = dist[ii][jj][x[b]][y[b]] + 1;
}
}
}
b++;
}
}
}
if (males < females) {
males++;
for (int i = 0; i < males; i++) {
scanf("%d %d %d", mx + i, my + i, mspeed + i);
}
for (int i = 0; i < females; i++) {
scanf("%d %d %d", fx + i, fy + i, fspeed + i);
}
} else {
females++;
for (int i = 0; i < 1; i++) {
scanf("%d %d %d", fx + i, fy + i, fspeed + i);
}
for (int i = 0; i < males; i++) {
scanf("%d %d %d", mx + i, my + i, mspeed + i);
}
for (int i = 1; i < females; i++) {
scanf("%d %d %d", fx + i, fy + i, fspeed + i);
}
}
long long low = 0, high = (long long)1e15;
while (low < high) {
long long mid = (low + high) >> 1;
if (can(mid)) {
high = mid;
} else {
low = mid + 1;
}
}
if (low == (long long)1e15) low = -1;
cout << low << endl;
return 0;
}
