#include <bits/stdc++.h>
using namespace std;
pair<bool, int> mat[503][503];
int dp[503][503];
int n, m, k, q;
int maxc;
bool moze(int l) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (mat[i][j].first && mat[i][j].second <= l) {
        dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
        if (dp[i][j] >= k) return true;
      } else
        dp[i][j] = 0;
    }
  }
  return false;
}
int bajnari(int a, int b) {
  if (a > b) return -1;
  int sred = (a + b) / 2;
  bool pom = moze(sred);
  if (pom) {
    if (!moze(sred - 1)) return sred;
    return bajnari(a, sred - 1);
  }
  if (!pom) {
    if (moze(sred + 1)) return sred + 1;
    return bajnari(sred + 1, b);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> k >> q;
  int qq = q;
  while (qq--) {
    int a, b, c;
    cin >> a >> b >> c;
    mat[a][b].first = true;
    mat[a][b].second = c;
    maxc = max(c, maxc);
  }
  cout << bajnari(0, maxc);
  return 0;
}
