#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000 + 1;
const int maxn = 500 + 1;
int n, m, k;
int q;
int jk[maxn][maxn];
int life[maxn][maxn];
bool baofei(int t) {
  int i, j;
  for (i = 1; i <= n; ++i)
    for (j = 1; j <= m; ++j) {
      life[i][j] = jk[i][j] - t;
      if (life[i][j] <= 0)
        life[i][j] = 1;
      else
        life[i][j] = 0;
    }
  for (i = 2; i <= n; ++i) life[i][1] += life[i - 1][1];
  for (j = 2; j <= m; ++j) life[1][j] += life[1][j - 1];
  for (i = 2; i <= n; ++i)
    for (j = 2; j <= m; ++j)
      life[i][j] += life[i - 1][j] + life[i][j - 1] - life[i - 1][j - 1];
  for (i = k; i <= n; ++i)
    for (j = k; j <= m; ++j) {
      int pi = i - k, pj = j - k;
      int scd = life[i][j] - life[pi][j] - life[i][pj] + life[pi][pj];
      if (scd == k * k) return true;
    }
  return false;
}
int main(int argc, char *argv[]) {
  if (argc >= 2) {
    freopen(argv[1], "r", stdin);
  }
  if (argc >= 3) {
    freopen(argv[2], "w", stdout);
  }
  scanf("%d%d%d", &n, &m, &k);
  scanf("%d", &q);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) jk[i][j] = INF;
  for (int _q = 0; _q < q; ++_q) {
    int x, y;
    int t;
    scanf("%d%d%d", &x, &y, &t);
    jk[x][y] = t;
  }
  int l = 0, r = INF, mid, ans = -1;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (baofei(mid))
      r = mid - 1, ans = mid;
    else
      l = mid + 1;
  }
  if (ans == INF) ans = -1;
  printf("%d", ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}
