#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
int vis[maxn][maxn];
int mp[maxn][maxn];
int n, m, k, q;
bool check(long long t) {
  memset(vis, 0, sizeof(vis));
  for (int j = 1; j <= m; j++) {
    int tep = 0;
    for (int i = n; i > 0; i--) {
      if (mp[i][j] <= t) {
        tep++;
      } else {
        tep = 0;
      }
      vis[i][j] = tep;
    }
  }
  for (int i = 1; i <= n - k + 1; i++) {
    int tep = 0;
    for (int j = 1; j <= m; j++) {
      if (vis[i][j] >= k)
        tep++;
      else
        tep = 0;
      if (tep >= k) {
        return true;
      }
    }
  }
  return false;
}
int main() {
  while (cin >> n >> m >> k >> q) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        mp[i][j] = 2e9 + 1;
      }
    }
    for (int i = 1; i <= q; i++) {
      int x, y, ti;
      scanf("%d%d%d", &x, &y, &ti);
      mp[x][y] = ti;
    }
    long long l = 0, r = 2e9, mid, ans = -1;
    while (l <= r) {
      mid = (l + r) / 2;
      if (check(mid)) {
        ans = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    printf("%lld\n", ans);
  }
}
