#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, k, q, l, r, mid, dp[N][N];
pair<int, pair<int, int> > a[N * N];
bool used[N][N];
inline bool check(int x) {
  memset(used, 0, sizeof(used));
  for (int i = 1; i <= q; i++) {
    if (a[i].second.second <= x) {
      used[a[i].first][a[i].second.first] = true;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (used[i][j]);
      if (i >= k && j >= k) {
        if (dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k] ==
            k * k) {
          return true;
        }
      }
    }
  }
  return false;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k >> q;
  for (int i = 1; i <= q; i++) {
    cin >> a[i].first >> a[i].second.first >> a[i].second.second;
  }
  l = 0, r = 1e9;
  while (r - l > 1) {
    mid = (r + l) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  if (check(l)) {
    cout << l;
  } else if (check(r)) {
    cout << r;
  } else {
    cout << "-1";
  }
}
