#include <stdio.h>
#include <stdlib.h>

#define MAX 501

int a[MAX][MAX];
int v[MAX];

int main(){
  FILE *fin, *fout;
  int q, n, m, k, l, c, i, j, sec, max, d, dp;

  fin = fopen("deminare.in", "r");

  fout = fopen("deminare.out", "w");

  fscanf(fin, "%d%d%d%d", &q, &n, &m, &k);
  for(i = 0; i < k; i++) {
    fscanf(fin, "%d%d", &l, &c);
    a[l][c] = 1;
  }

  for(i = 1; i <= n; i++) {
    for(j = 1; j <= m; j++)
      a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
  }
  if(q == 1) {
    sec = max = 0;
    for(i = 1; i <= n; i++) {
      sec = a[i][m] - a[i - 1][m];
      if(sec > max) {
        max = sec;
        for(j = 1; j < i; j++)
          v[j] = 0;
        v[i] = 1;
      }
      else if(sec == max)
        v[i] = 1;
    }
    for(i = 1; i <= n; i++) {
      if(v[i] == 1)
        fprintf(fout, "%d\n", i);
    }
  }
  else {
    max = sec = 0;
    for(d = 1; d <= k / 2; d++) {
      if(k % d == 0) {
        dp = k / d;
        for(l = d; l <= n; l++) {
          for(c = dp; c <= m; c++) {
            sec = a[l][c] - a[l][c - dp] - a[l - d][c] + a[l - d][c - dp];
            if(sec > max)
              max = sec;
          }
        }
        for(l = dp; l <= n; l++) {
          for(c = d; c <= m; c++) {
            sec = a[l][c] - a[l][c - d] - a[l - dp][c] + a[l - dp][c - d];
            if(sec > max)
              max = sec;
          }
        }
      }
    }
    if(max == 0)
      max = k + 1;
    fprintf(fout, "%d\n", k - max);
  }


  fclose(fin);
  fclose(fout);

  return 0;
}