Dinic_AC

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

template <typename FlowType>
class FlowGraph {
public:
  class Edge {
  public:
    Edge() = default;

    Edge(int from, int to, FlowType cap)
        : from_(from),
          to_(to),
          capacity_(cap) {
    }

    [[nodiscard]]
    inline FlowType GetPotential() const {
      return capacity_ - flow_;
    }

    int from_;
    int to_;
    FlowType flow_{};
    FlowType capacity_;
  };

  FlowGraph(int start,
            int terminal,
            int vertices,
            int edges = -1)
      : start_(start),
        terminal_(terminal),
        n_(vertices),
        adj_(vertices),
        distance_(vertices),
        first_alive_edge_(vertices) {
    if (edges != -1) {
      edges_.reserve(edges * 2);
    }
  }

  inline int AddDirectedEdge(int from, int to, FlowType cap) {
    edges_.emplace_back(from, to, cap);
    adj_[from].emplace_back(size(edges_) - 1);
    edges_.emplace_back(to, from, 0);
    adj_[to].emplace_back(size(edges_) - 1);
    return adj_[from].back();
  }

  inline int AddBidirectionalEdge(int from, int to, FlowType cap) {
    edges_.emplace_back(from, to, cap);
    adj_[from].emplace_back(size(edges_) - 1);
    edges_.emplace_back(to, from, cap);
    adj_[to].emplace_back(size(edges_) - 1);
    return adj_[from].back();
  }

  [[nodiscard]]
  inline std::optional <Edge> GetEdge(size_t id) {
    if (id < size(edges_)) {
      return edges_[id];
    } else {
      return std::nullopt;
    }
  }

  /* Computes maximal flow in O(V^2 * E) */
  FlowType Dinic() {
    FlowType augment;
    FlowType max_flow = 0;

    while (Bfs()) {
      while ((augment = Dfs(start_, std::numeric_limits <FlowType>::max())) > 0) {
        max_flow += augment;
      }
    }

    return max_flow;
  }

  /* Computes maximal flow in O(VE * log(C)), where C is the maximal single edge capacity in the network*/
  FlowType ScalingDinic() {
    FlowType max_capacity = 0;
    for (const Edge& e : edges_) {
      max_capacity = std::max(max_capacity, e.GetCapacity());
    }

    while (lower_bound_ * 2 <= max_capacity) {
      lower_bound_ *= 2;
    }

    FlowType max_flow = 0;
    while (lower_bound_ > 0) {
      max_flow += Dinic();
      lower_bound_ /= 2;
    }

    return max_flow;
  }

  /* O(E)
   * Yields edges which are present in minimal cut between start and terminal and size of minimal cut
   * Make sure you've called Dinic() before calling this */
  std::pair <std::vector <Edge>, FlowType> MinCut() {
    std::vector <char> reachable(n_);

    auto Dfs = [&](const auto& Self, int node) -> void {
      reachable[node] = true;
      for (const int& id : adj_[node]) {
        Edge& e = edges_[id];
        if (!reachable[e.to_] && e.GetPotential() > 0) {
          Self(Self, e.to_);
        }
      }
    };

    Dfs(Dfs, start_);
    FlowType min_cut_size = 0;
    std::vector <Edge> answer;

    for (int i = 0; i < size(edges_) / 2; ++i) {
      if (reachable[edges_[i * 2].to_] ^ reachable[edges_[i * 2 + 1].to_]) {
        if (reachable[edges_[i * 2].to_]) {
          answer.push_back(edges_[i * 2 + 1]);
        } else {
          answer.push_back(edges_[i * 2]);
        }
        min_cut_size += std::max(edges_[i * 2].flow_, edges_[i * 2 + 1].flow_);
      }
    }

    return {answer, min_cut_size};
  }

  /* Decomposes the found flow to paths. Runs in O(VE) */
  std::vector <std::pair <std::vector <int>, FlowType>> FlowDecomposition() {
    std::vector <int> path;
    std::vector <std::pair <std::vector <int>, FlowType>> decomposition;

    int timer = 0;
    std::vector <int> used(n_, -1);
    std::fill(begin(first_alive_edge_), end(first_alive_edge_), 0);

    auto Dfs = [&](const auto& Self, int node, FlowType path_min) -> FlowType {
      if (node == terminal_) {
        path.emplace_back(node);
        return path_min;
      }

      if (used[node] == timer) {
        return path_min;
      }

      int id;
      FlowType taken;
      used[node] = timer;
      int& start = first_alive_edge_[node];

      for (int i = start; i < size(adj_[node]); ++i) {
        id = adj_[node][i];
        Edge& e = edges_[id];
        Edge& e_rev = edges_[id ^ 1];
        if (e.flow_ > 0 && (taken = Self(Self, e.to_, std::min(path_min, e.flow_))) > 0) {
          path.emplace_back(node);
          e.flow_ -= taken;
          e_rev.flow_ += taken;
          if (e.flow_ == 0) {
            start += 1;
          }
          return taken;
        } else {
          start += 1;
        }
      }

      return 0;
    };

    FlowType taken;
    while ((taken = Dfs(Dfs, start_, std::numeric_limits <FlowType>::max())) > 0) {
      timer += 1;
      std::reverse(begin(path), end(path));
      decomposition.emplace_back(path, taken);
      path.clear();
    }

    return decomposition;
  }

private:
  bool Bfs() {
    std::fill(begin(distance_), end(distance_), -1);

    distance_[start_] = 0;
    auxiliary_queue_.push(start_);
    while (!auxiliary_queue_.empty()) {
      int node = auxiliary_queue_.front();
      auxiliary_queue_.pop();
      for (const int& id : adj_[node]) {
        Edge& e = edges_[id];
        if (distance_[e.to_] == -1
            && lower_bound_ <= e.GetPotential()) {
          distance_[e.to_] = distance_[node] + 1;
          auxiliary_queue_.push(e.to_);
        }
      }
    }

    if (distance_[terminal_] == -1) {
      return false;
    }
    std::fill(begin(first_alive_edge_), end(first_alive_edge_), 0);
    return true;
  }

  FlowType Dfs(int node, FlowType augment) {
    if (node == terminal_) {
      return augment;
    }

    int id;
    FlowType pushed;
    int& start = first_alive_edge_[node];

    for (int i = start; i < size(adj_[node]); ++i) {
      id = adj_[node][i];
      Edge& e = edges_[id];
      Edge& e_rev = edges_[id ^ 1];

      if (distance_[node] + 1 != distance_[e.to_]
          || e.GetPotential() < lower_bound_) {
        start += 1;
        continue;
      }

      pushed = Dfs(e.to_, std::min(augment, e.GetPotential()));
      if (pushed > 0) {
        e.flow_ += pushed;
        e_rev.flow_ -= pushed;
        if (e.GetPotential() < lower_bound_) {
          start += 1;
        }
        return pushed;
      } else {
        start += 1;
      }
    }

    return 0;
  }

  const int start_;
  const int terminal_;

  FlowType lower_bound_ = 1;

  int n_;
  std::vector <Edge> edges_;
  std::vector <int> distance_;
  std::queue <int> auxiliary_queue_;
  std::vector <int> first_alive_edge_;
  std::vector <std::vector <int>> adj_;
};

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) {
      if (c == '*') {
        vacant += 1;
      }
    }
  }

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

  FlowGraph <int> network(n * m, n * m + 1, n * m + 2, n * m + n * m * 2 + 2);

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

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

      if ((i + j) % 2 == 1) {
        network.AddDirectedEdge(i * m + j, n * m + 1, 1);
        continue;
      }

      network.AddDirectedEdge(n * m, i * m + j, 1);
      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] != '.') {
          network.AddDirectedEdge(i * m + j, new_i * m + new_j, 1);
        }
      }
    }
  }

  int mat = network.Dinic();
  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;
}