deminare

// prof. Maria Pandele - 100 puncte

#include <cmath>
#include <fstream>
#include <vector>

int solve1(std::vector<std::vector<int>>& a, std::ofstream& cout) {
  int maxim = 0;
  std::vector<int> cnt(a.size());
  for (int i = 0; i < a.size(); ++i) {
    cnt[i] = 0;
    for (int j = 0; j < a[i].size(); ++j) {
      cnt[i] += a[i][j];
    }
    maxim = std::max(maxim, cnt[i]);
  }

  for (int i = 0; i < cnt.size(); ++i) {
    if (cnt[i] == maxim) {
      cout << i + 1 << " ";
    }
  }
  cout << "\n";
}

int verif(std::vector<std::vector<int>>& sp, int& l, int &c, int&h , int& w) {
  int ans = -1;

  if (h <= l && w <= c) {
    for (int i = 1; i <= l - h + 1; ++i) {
      for (int j = 1; j <= c - w + 1; ++j) {
        int x = i + h - 1;
        int y = j + w - 1;
        ans = std::max(ans, sp[x][y] - sp[i - 1][y] - sp[x][j - 1] + sp[i - 1][j - 1]);
      }
    }
  }
  return ans;
}

int solve2(std::vector<std::vector<int>>& a, int& l, int& c, int& m) {
  std::vector<std::vector<int>> sp(l + 1, std::vector<int>(c + 1, 0));
  for (int i = 0; i < l; ++i) {
    sp[i][0] = a[i][0];
  }

  for (int j = 0; j < c; ++j) {
    sp[0][j] = a[0][j];
  }

  for (int i = 1; i <= l; ++i) {
    for (int j = 1; j <= c; ++j) {
      sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + a[i - 1][j - 1];
    }
  }

  int lim = sqrt(m);
  int ans = -1;
  for (int d = 1; d <= lim; ++d) {
    if (m % d == 0) {
      int h = d;
      int w = m / d;

      ans = std::max(ans, verif(sp, l, c, h, w));
      ans = std::max(ans, verif(sp, l, c, w, h));
    }
  }
  if (ans == -1) {
    return -1;
  }
  return m - ans;
}

int main() {
  std::ifstream cin("deminare.in");
  std::ofstream cout("deminare.out");

  int v, l, c, m;
  cin >> v >> l >> c >> m;
  std::vector<std::vector<int>> a(l, std::vector<int>(c, 0));
  int x, y;
  for (int i = 0; i < m; ++i) {
    cin >> x >> y;
    --x; --y;
    a[x][y] = 1;
  }

  if (v == 1) {
    solve1(a, cout);
  }
  else {
    cout << solve2(a, l, c, m) << "\n";
  }
  return 0;
}