#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 3;
const int MAXT = 1000000000;
int N, M, K, Q;
int y[MAXN * MAXN], x[MAXN * MAXN], t[MAXN * MAXN];
int sum[MAXN][MAXN];
bool judge(int mid) {
  memset(sum, 0, sizeof(sum));
  for (int i = 0; i < Q; ++i)
    if (t[i] <= mid) sum[y[i]][x[i]] = 1;
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= M; ++j) {
      sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
      if (i >= K && j >= K &&
          sum[i][j] - sum[i - K][j] - sum[i][j - K] + sum[i - K][j - K] ==
              K * K)
        return true;
    }
  return false;
}
int main() {
  scanf("%d%d%d%d", &N, &M, &K, &Q);
  for (int i = 0; i < Q; ++i) scanf("%d%d%d", &y[i], &x[i], &t[i]);
  int l = -1, r = MAXT + 1;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (judge(mid))
      r = mid;
    else
      l = mid;
  }
  printf("%d\n", r == MAXT + 1 ? -1 : r);
  return 0;
}
