#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
const int inf = 2e9;
multiset<int> s;
int a[505][505], mn[505][505];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m >> k >> q;
  for (int i = 1; i < n + 1; i++)
    for (int j = 1; j < m + 1; j++) a[i][j] = inf;
  if (n < k || m < k) {
    cout << -1;
    return 0;
  }
  while (q--) {
    int x, y, z;
    cin >> x >> y >> z;
    a[x][y] = z;
  }
  for (int i = 1; i < m + 1; i++) {
    s.clear();
    for (int j = 1; j <= k; j++) {
      s.insert(a[j][i]);
    }
    for (int j = 1; j <= n - k + 1; j++) {
      mn[j][i] = *s.rbegin();
      s.erase(s.lower_bound(a[j][i]));
      s.insert(a[j + k][i]);
    }
  }
  int re = inf;
  for (int i = 1; i <= n - k + 1; i++) {
    s.clear();
    for (int j = 1; j <= k; j++) {
      s.insert(mn[i][j]);
    }
    for (int j = 1; j <= m - k + 1; j++) {
      int x = *s.rbegin();
      if (x < inf) re = min(re, x);
      s.erase(s.lower_bound(mn[i][j]));
      s.insert(mn[i][j + k]);
    }
  }
  if (re == inf) {
    cout << -1;
    return 0;
  }
  cout << re;
}
