#include <bits/stdc++.h>
int main() {
  std::priority_queue<std::tuple<int, int, int>> queue;
  int h, w, n, r;
  char c[64];
  int values[64];
  int st;
  std::unordered_map<char, int> m;
  std::cin >> h >> w >> n >> r;
  for (int y = 0; y < h; ++y) {
    for (int x = 0; x < w; ++x) {
      std::cin >> c[x + w * y];
      values[x + w * y] = -1;
      if (c[x + w * y] == '@') {
        st = x + w * y;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    int value;
    char key;
    std::cin >> key >> value;
    m.emplace(key, value);
  }
  std::vector<std::unordered_set<int>> tresures;
  tresures.emplace({});
  queue.emplace(std::make_tuple(0, st, 0));
  while (!queue.empty()) {
    auto item = queue.top();
    int score = std::get<0>(item);
    int pos = std::get<1>(item);
    std::unordered_set<int> tresure = tresures[std::get<2>(item)];
    queue.pop();
    int x = pos % w;
    int y = pos / w;
    for (int i : {0, 1}) {
      for (int j : {-1, 1}) {
        int dx, dy;
        if (i == 0) {
          dx == 0;
          dy = j;
        } else {
          dy = 0;
          dx = j;
        }
        if (x + dx >= 0 && x + dx < w && y + dy >= 0 && y + dy < h) {
          int new_pos = (x + dx) + (y + dy) * w;
          char field = c[new_pos];
          if (field == '#') {
            continue;
          }
          if (field != '.' && field != '@') {
            if (tresure.find(new_pos) != tresure.end()) {
              continue;
            }
            if (field == '*') {
              score -= r;
            } else {
              score += m[field];
            }
            tresure.insert(new_pos);
          }
          if (score > values[new_pos]) {
            values[new_pos] = score;
            tresures.push_back(tresure);
            queue.emplace(score, new_pos, tresures.size() - 1);
          }
        }
      }
    }
  }
  int max_score = 0;
  for (int i = 0; i < w * h; ++i) {
    if (max_score < values[i]) {
      max_score = values[i];
    }
  }
  std::cout << max_score << std::endl;
  return 0;
}
