#include <bits/stdc++.h>
using namespace std;
using namespace std;
int n, m;
int a[1024][1024], st[2 * 1024][2 * 1024];
long long dp[1024][1024];
void build() {
  for (int i = 0, ThxDem = n; i < ThxDem; ++i)
    for (int j = 0, ThxDem = m; j < ThxDem; ++j) st[i + n][j + m] = a[i][j];
  for (int i = 0, ThxDem = n; i < ThxDem; ++i)
    for (int j = m - 1; j; --j)
      st[i + n][j] = max(st[i + n][j << 1], st[i + n][j << 1 | 1]);
  for (int i = n - 1; i; --i)
    for (int j = 0, ThxDem = 2 * m; j < ThxDem; ++j)
      st[i][j] = max(st[i << 1][j], st[i << 1 | 1][j]);
}
void upd(int x, int y, int v) {
  st[x + n][y + m] = v;
  for (int j = y + m; j > 1; j >>= 1)
    st[x + n][j >> 1] = max(st[x + n][j], st[x + n][j ^ 1]);
  for (int i = x + n; i > 1; i >>= 1)
    for (int j = y + m; j; j >>= 1) st[i >> 1][j] = max(st[i][j], st[i ^ 1][j]);
}
int query(int x0, int x1, int y0, int y1) {
  int r = 0;
  for (int i0 = x0 + n, i1 = x1 + n; i0 < i1; i0 >>= 1, i1 >>= 1) {
    int t[4], q = 0;
    if (i0 & 1) t[q++] = i0++;
    if (i1 & 1) t[q++] = --i1;
    for (int k = 0, ThxDem = q; k < ThxDem; ++k)
      for (int j0 = y0 + m, j1 = y1 + m; j0 < j1; j0 >>= 1, j1 >>= 1) {
        if (j0 & 1) r = max(r, st[t[k]][j0++]);
        if (j1 & 1) r = max(r, st[t[k]][--j1]);
      }
  }
  return r;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int k, q;
  cin >> n >> m >> k >> q;
  memset(st, 0, sizeof(st));
  while (q--) {
    int x, y, t;
    cin >> x >> y >> t;
    dp[x - 1][y - 1] = 1;
    upd(x - 1, y - 1, t);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i - 1 >= 0) dp[i][j] += dp[i - 1][j];
      if (j - 1 >= 0) dp[i][j] += dp[i][j - 1];
      if (j - 1 >= 0 && i - 1 >= 0) dp[i][j] -= dp[i - 1][j - 1];
    }
  }
  int ans = (1e9 + 7);
  for (int i = 0; i + k - 1 < n; i++) {
    for (int j = 0; j + k - 1 < m; j++) {
      int cnt = dp[i + k - 1][j + k - 1];
      if (i - 1 >= 0) cnt -= dp[i - 1][j + k - 1];
      if (j - 1 >= 0) cnt -= dp[i + k - 1][j - 1];
      if (i - 1 >= 0 && j - 1 >= 0) cnt += dp[i - 1][j - 1];
      if (cnt == k * k) {
        ans = min(ans, query(i, i + k, j, j + k));
      }
    }
  }
  cout << (ans == (int)((1e9 + 7)) ? -1 : ans) << '\n';
  return 0;
}
