#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 1;
const int MAXN = 501;
int k, Q;
int n, m, cnt[MAXN][MAXN];
vector<pair<int, pair<int, int> > > V;
bool first(int t) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < (int)Q; i++)
    if (V[i].first <= t) cnt[V[i].second.first][V[i].second.second]++;
  for (int r = 1; r < (int)n + 1; r++)
    for (int c = 1; c < (int)m + 1; c++)
      cnt[r][c] += cnt[r - 1][c] + cnt[r][c - 1] - cnt[r - 1][c - 1];
  for (int r = k; r < (int)n + 1; r++)
    for (int c = k; c < (int)m + 1; c++)
      if (cnt[r][c] - cnt[r - k][c] - cnt[r][c - k] + cnt[r - k][c - k] ==
          k * k)
        return true;
  return false;
}
int main() {
  cin >> n >> m >> k >> Q;
  for (int i = 0; i < (int)Q; i++) {
    int r, c, t;
    scanf("%d", &r), scanf("%d", &c), scanf("%d", &t);
    V.push_back({t, {r, c}});
  }
  int lo = 0, hi = 1e9 + 1;
  while (lo < hi) {
    int med = (lo + hi) / 2;
    if (first(med))
      hi = med;
    else
      lo = med + 1;
  }
  printf("%d\n", lo == INF ? -1 : lo);
}
