#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > tab;
int cx[300010], cy[300010], t, n, i, q, m, k;
bool pixels[1010][1010];
int dp[1010][1010];
bool is() {
  for (int a = 1; a <= n; a++)
    for (int b = 1; b <= m; b++) dp[a][b] = 0;
  for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= m; b++) {
      if (!pixels[a][b]) continue;
      i = min(dp[a - 1][b], dp[a][b - 1]);
      if (pixels[a][b] && pixels[a - i][b - i])
        dp[a][b] = i + 1;
      else
        dp[a][b] = i;
      if (dp[a][b] >= k) return 1;
    }
  }
  return 0;
}
bool ok(int v) {
  for (int a = 1; a <= n; a++)
    for (int b = 1; b <= m; b++) pixels[a][b] = 0;
  for (int a = 0; a < tab.size(); a++) {
    if (tab[a].first > v) break;
    pixels[cx[tab[a].second]][cy[tab[a].second]] = 1;
  }
  return is();
}
int bs(int pocz, int kon) {
  if (pocz == kon) return pocz;
  int mid = (pocz + kon) / 2;
  if (ok(mid)) return bs(pocz, mid);
  return bs(mid + 1, kon);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k >> q;
  for (int a = 1; a <= q; a++) {
    cin >> cx[a] >> cy[a] >> t;
    tab.push_back(make_pair(t, a));
    pixels[cx[a]][cy[a]] = 1;
  }
  if (is() == 0) {
    cout << "-1";
    return 0;
  }
  sort(tab.begin(), tab.end());
  cout << bs(0, 1e9 + 1);
  return 0;
}
