#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int a[maxn][maxn], pref[maxn][maxn], row[maxn][maxn];
int n, m, k, q;
struct DATA {
  int x, y, t;
};
DATA p[maxn * maxn];
int get(int x1, int y1, int x2, int y2) {
  int ret =
      pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
  return ret;
}
bool can(int x) {
  memset(a, 0, sizeof a);
  for (int i = 1; i <= x; ++i) {
    a[p[i].x][p[i].y] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      row[i][j] = row[i][j - 1] + a[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      pref[i][j] = pref[i - 1][j] + row[i][j];
    }
  }
  for (int i = 1; i + k - 1 <= n; ++i) {
    for (int j = 1; j + k - 1 <= m; ++j) {
      if (get(i, j, i + k - 1, j + k - 1) == k * k) {
        return 1;
      }
    }
  }
  return 0;
}
int main(int argc, char const *argv[]) {
  scanf("%d %d %d %d", &n, &m, &k, &q);
  for (int i = 1; i <= q; ++i) {
    scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].t);
  }
  sort(p + 1, p + q + 1, [&](DATA x, DATA y) { return x.t < y.t; });
  int lo = 1, hi = q, ans = -1;
  while (lo <= hi) {
    int mid = (lo + hi) >> 1;
    if (can(mid)) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  if (ans == -1) {
    printf("-1\n");
  } else {
    printf("%d\n", p[ans].t);
  }
  return 0;
}
