#include <bits/stdc++.h>
using namespace std;
vector<vector<char>> grid;
vector<pair<int, int>> wind;
int n, m;
int k;
int t;
int w;
unordered_map<char, pair<int, int>> charToDir;
vector<pair<int, int>> dirs({pair<int, int>(1, 0), pair<int, int>(-1, 0),
                             pair<int, int>(0, 1), pair<int, int>(0, -1),
                             pair<int, int>(0, 0)});
pair<int, int> getLocation(char c) {
  for (int i = 0; i < ((int)(grid).size()); ++i)
    for (int j = 0; j < ((int)(grid[i]).size()); ++j) {
      if (grid[i][j] == c) {
        return pair<int, int>(i, j);
      }
    }
  assert(false);
  return pair<int, int>(0, 0);
}
bool legal(pair<int, int> a) {
  int i = a.first;
  int j = a.second;
  return !(i < 0 || j < 0 || i >= n || j >= m) && grid[i][j] != 'L';
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  charToDir['S'] = pair<int, int>(1, 0);
  charToDir['N'] = pair<int, int>(-1, 0);
  charToDir['E'] = pair<int, int>(0, 1);
  charToDir['W'] = pair<int, int>(0, -1);
  charToDir['X'] = pair<int, int>(0, 0);
  cin >> n >> m;
  cin >> k;
  cin >> t;
  cin >> w;
  grid.resize(n, vector<char>(m));
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j < (m); ++j) cin >> grid[i][j];
  wind.resize(w);
  for (int i = 0; i < (w); ++i) {
    char c;
    cin >> c;
    wind[i] = charToDir[c];
  }
  vector<vector<vector<bool>>> shop(4010,
                                    vector<vector<bool>>(n, vector<bool>(m)));
  for (int i = 0; i < (t); ++i) {
    int y, x, f;
    cin >> y >> x >> f;
    shop[f][y][x] = true;
  }
  pair<int, int> startLocation = getLocation('M');
  pair<int, int> goal = getLocation('P');
  vector<vector<int>> maxFood(n, vector<int>(m, -1));
  maxFood[startLocation.first][startLocation.second] = k;
  for (int d = 0; d < (w); ++d) {
    vector<vector<int>> newMaxFood(n, vector<int>(m, -1));
    bool changedSomething = false;
    for (int i = 0; i < (n); ++i)
      for (int j = 0; j < (m); ++j)
        if (maxFood[i][j] > 0) {
          for (auto& movement : dirs) {
            int newI = i + movement.first;
            int newJ = j + movement.second;
            pair<int, int> a(newI, newJ);
            pair<int, int> windMovement = wind[d];
            newI += windMovement.first;
            newJ += windMovement.second;
            pair<int, int> b(i + windMovement.first, j + windMovement.second);
            if (newI != i || newJ != j) {
              if (!legal(a) && !legal(b)) continue;
              if (!legal(pair<int, int>(newI, newJ))) continue;
            }
            newMaxFood[newI][newJ] =
                max(newMaxFood[newI][newJ], maxFood[i][j] - 1);
            changedSomething = true;
            if (shop[d + 1][newI][newJ]) {
              newMaxFood[newI][newJ] = k;
            }
            if (pair<int, int>(newI, newJ) == goal) {
              cout << d + 1 << endl;
              return 0;
            }
          }
        }
    if (!changedSomething) {
      cout << -1 << endl;
      return 0;
    }
    maxFood = newMaxFood;
  }
  cout << -1 << endl;
}
