#include <bits/stdc++.h>
int main() {
  std::priority_queue<std::tuple<int, int, std::vector<int>>> queue;
  int h, w, n, r;
  char c[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];
      if (c[x + w * y] == '@') {
        st = x + w * y;
      }
    }
  }
  std::vector<int> cost(h * w, -r * h * w - 1);
  for (int i = 0; i < n; ++i) {
    char key;
    int gold;
    std::cin >> key >> gold;
    m.emplace(key, gold);
  }
  queue.emplace(0, st, std::vector<int>(h * w, 0));
  int max_score = 0;
  while (!queue.empty()) {
    auto item = queue.top();
    queue.pop();
    auto score = std::get<0>(item);
    auto pos = std::get<1>(item);
    auto stayed = std::get<2>(item);
    int x = pos % w;
    int y = pos / w;
    for (int j : {0, 1}) {
      for (int k : {-1, 1}) {
        int dx, dy;
        if (j == 0) {
          dx = 0;
          dy = k;
        } else {
          dx = k;
          dy = 0;
        }
        int new_x = x + dx;
        int new_y = y + dy;
        if (new_x >= 0 && new_x < w && new_y >= 0 && new_y < h) {
          auto stayed_copied = stayed;
          int new_pos = new_x + new_y * w;
          if (stayed_copied[new_pos] >= 2) {
            continue;
          }
          char field = c[new_pos];
          if (field == '#') {
            continue;
          }
          int new_score = score;
          if (stayed_copied[new_pos] == 0) {
            if (field == '*') {
              new_score -= r;
            } else if (field != '.' && field != '@') {
              new_score += m[field];
            }
          }
          if (cost[new_pos] <= new_score) {
            stayed_copied[new_pos] += 1;
            cost[new_pos] = new_score;
            queue.emplace(new_score, new_pos, stayed_copied);
            if (max_score < new_score) {
              max_score = new_score;
            }
          }
        }
      }
    }
  }
  std::cout << max_score << std::endl;
  return 0;
}
