#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
int n, m, k, q;
int t[N << 2][N << 2], a[N][N];
void ins2(int x, int u, int l, int r, int pos, int v) {
  t[x][u] = max(t[x][u], v);
  if (l == r) return;
  int mid = (l + r) / 2;
  if (pos <= mid)
    ins2(x, u << 1, l, mid, pos, v);
  else
    ins2(x, u << 1 | 1, mid + 1, r, pos, v);
}
void ins(int u, int l, int r, int x, int y, int v) {
  ins2(u, 1, 1, m, y, v);
  if (l == r) return;
  int mid = (l + r) / 2;
  if (x <= mid)
    ins(u << 1, l, mid, x, y, v);
  else
    ins(u << 1 | 1, mid + 1, r, x, y, v);
}
int query2(int x, int u, int l, int r, int L, int R) {
  if (l == L && r == R) return t[x][u];
  int mid = (l + r) / 2;
  if (R <= mid)
    return query2(x, u << 1, l, mid, L, R);
  else if (L > mid)
    return query2(x, u << 1 | 1, mid + 1, r, L, R);
  else
    return max(query2(x, u << 1, l, mid, L, mid),
               query2(x, u << 1 | 1, mid + 1, r, mid + 1, R));
}
int query(int u, int l, int r, int xl, int xr, int yl, int yr) {
  if (l == xl && r == xr) return query2(u, 1, 1, m, yl, yr);
  int mid = (l + r) / 2;
  if (xr <= mid)
    return query(u << 1, l, mid, xl, xr, yl, yr);
  else if (xl > mid)
    return query(u << 1 | 1, mid + 1, r, xl, xr, yl, yr);
  else
    return max(query(u << 1, l, mid, xl, mid, yl, yr),
               query(u << 1 | 1, mid + 1, r, mid + 1, xr, yl, yr));
}
int main() {
  scanf("%d%d%d%d", &n, &m, &k, &q);
  memset(a, 0x3f, sizeof(a));
  while (q--) {
    int x, y, T;
    scanf("%d%d%d", &x, &y, &T);
    a[x][y] = T;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) ins(1, 1, n, i, j, a[i][j]);
  int ans = INF;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (i + k - 1 <= n && j + k - 1 <= m) {
        ans = min(ans, query(1, 1, n, i, i + k - 1, j, j + k - 1));
      }
  printf("%d\n", ans == INF ? -1 : ans);
  return 0;
}
