#include <bits/stdc++.h>
using namespace std;
long long n, m, k, q, x[1000001], y[1000001], t[1000001], a[501][501],
    dp[501][501];
bool chek(long long v) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) a[i][j] = 0;
  for (int i = 1; i <= q; i++) {
    if (t[i] <= v) a[x[i]][y[i]] = 1;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) dp[i][j] = dp[i][j - 1] + a[i][j];
  for (int i = 1; i <= n - k + 1; i++) {
    for (int j = 1; j <= m - k + 1; j++) {
      long long s = 0;
      for (int g = i; g <= i + k - 1; g++)
        s = s + dp[g][j + k - 1] - dp[g][j - 1];
      if (s == k * k) return 1;
    }
  }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long i, j, l, r, h;
  cin >> n >> m >> k >> q;
  for (i = 1; i <= q; i++) cin >> x[i] >> y[i] >> t[i];
  l = 0;
  r = 1e9;
  while (l + 1 < r) {
    h = (l + r) / 2;
    if (chek(h) == 1)
      r = h;
    else
      l = h;
  }
  if (chek(l) == 1)
    cout << l;
  else if (chek(r) == 1)
    cout << r;
  else
    cout << -1;
}
