#include <bits/stdc++.h>
int fun(int mid);
int n, m, k, q;
int a[505][505];
int x[250050], y[250050], t[250050];
int max;
int main() {
  scanf("%d%d%d%d", &n, &m, &k, &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d%d", &x[i], &y[i], &t[i]);
    max = (max > t[i] ? max : t[i]);
  }
  int l = 0, r = max, mid;
  while (l <= r) {
    mid = l + r >> 1;
    if (fun(mid)) {
      r = mid - 1;
    } else
      l = mid + 1;
  }
  if (r + 1 > max)
    printf("-1\n");
  else
    printf("%d\n", r + 1);
}
int fun(int mid) {
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++) a[i][j] = 0;
  for (int i = 1; i <= q; i++) {
    if (t[i] <= mid) a[x[i]][y[i]] = 1;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
      if (i >= k && j >= k &&
          (a[i][j] + a[i - k][j - k] - a[i][j - k] - a[i - k][j]) == k * k)
        return 1;
    }
  return 0;
}
