#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long d[503][503];
long long dp[503][503];
long long c[503][503];
int n, m, k, q;
int kk;
void hh(int x) {
  for (int i = 0; i < m; i++) dp[i][0] = d[x][i];
  for (int j = 1; (1 << j) <= m; j++)
    for (int i = 0; i + (1 << j) - 1 < m; i++)
      dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
  for (int i = 0; i <= m - k; i++)
    c[x][i] = max(dp[i][kk], dp[i + k - (1 << kk)][kk]);
}
int RMQ(int l, int r) {
  int kk = 0;
  while ((1 << (kk + 1)) <= r - l + 1) kk++;
  return kk;
  ;
}
int main() {
  cin >> n >> m >> k >> q;
  kk = RMQ(1, k);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) d[i][j] = INF;
  for (int i = 1; i <= q; i++) {
    int x, y;
    long long t;
    scanf("%d%d%lld", &x, &y, &t);
    d[x - 1][y - 1] = t;
  }
  for (int i = 0; i < n; i++) hh(i);
  long long MMax = INF;
  for (int i = 0; i <= n - k; i++) {
    for (int j = 0; j <= m - k; j++) {
      long long Max = -1;
      for (int kk = i; kk <= i + k - 1; kk++) {
        Max = max(Max, c[kk][j]);
        if (Max == INF) break;
      }
      MMax = min(MMax, Max);
    }
  }
  if (MMax == INF)
    cout << -1 << endl;
  else
    cout << MMax << endl;
}
