Kuhn_AC

#include <bits/stdc++.h>
using namespace std;

class Matching {
public:
  int left_;
  int right_;
  int pairs_;
  vector <int> used_;
  vector <int> match_left_;
  vector <int> match_right_;
  vector <vector <int>> adj_;

  explicit Matching(int n, int m)
      : left_(n),
        right_(m),
        adj_(n),
        used_(n),
        pairs_(0),
        match_left_(n, -1),
        match_right_(m, -1) {
  }

  [[gnu::always_inline]]
  inline void AddEdge(int left, int right) {
    adj_[left].emplace_back(right);
  }

  bool Dfs(int node) {
    if (used_[node] == pairs_ + 1) {
      return false;
    }
    used_[node] = pairs_ + 1;
    for (const int& to : adj_[node]) {
      if (match_right_[to] == -1) {
        match_left_[node] = to;
        match_right_[to] = node;
        return true;
      }
    }

    for (const int& to : adj_[node]) {
      if (Dfs(match_right_[to])) {
        match_left_[node] = to;
        match_right_[to] = node;
        return true;
      }
    }

    return false;
  }

  template <bool Shuffle = false>
  vector <pair <int, int>> Solve() {
    vector <int> order(left_);
    iota(order.begin(), order.end(), 0);

    if constexpr (Shuffle) {
      shuffle(order.begin(), order.end(), mt19937(chrono::steady_clock::now().time_since_epoch().count()));
      for (vector <int>& adj_list : adj_) {
        shuffle(adj_list.begin(), adj_list.end(), mt19937(chrono::steady_clock::now().time_since_epoch().count()));
      }
    }

    for (const int& node : order) {
      pairs_ += Dfs(node);
    }

    vector <pair <int, int>> result;
    result.reserve(pairs_);
    for (int i = 0; i < left_; ++i) {
      if (match_left_[i] != -1) {
        result.emplace_back(i, match_left_[i]);
      }
    }

    return result;
  }
};

void RunCase() {
  int n, m, a, b;
  cin >> n >> m >> a >> b;

  vector <vector <char>> grid(n, vector <char>(m));
  for (auto& row : grid) {
    for (auto& c : row) {
      cin >> c;
    }
  }

  int vacant = 0;
  for (const auto& row : grid) {
    for (const auto& c : row) {
      vacant += (c == '*');
    }
  }

  if (vacant == 0) {
    cout << "0\n";
    return;
  }

  if (2 * b <= a) {
    cout << vacant * b * 2 << "\n";
    return;
  }

  const int grid_size = n * m;
  Matching matching(grid_size / 2 + grid_size % 2, grid_size / 2);

  constexpr int dx[] = {-1, 0, 0, 1};
  constexpr int dy[] = {0, -1, 1, 0};

  vector <int> code(n * m);
  for (int i = 2; i < n * m; ++i) {
    code[i] = code[i - 2] + 1;
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i % 2; j < m; j += 2) {
      if (grid[i][j] == '.') {
        continue;
      }

      for (size_t k = 0; k < 4; ++k) {
        int new_i = i + dx[k];
        int new_j = j + dy[k];
        if (0 <= new_i && new_i <= n - 1
        && 0 <= new_j && new_j <= m - 1
        && grid[new_i][new_j] != '.') {
          matching.AddEdge(code[i * m + j], code[new_i * m + new_j]);
        }
      }
    }
  }

  int mat = matching.Solve().size();
  assert(mat * 2 <= vacant);
  cout << mat * a + b * (vacant - 2 * mat) << "\n";
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int tt = 1;
  //std::cin >> tt;
  while (tt--) {
    RunCase();
  }
  return 0;
}