#include <bits/stdc++.h>
using namespace std;
struct _ {
  ios_base::Init i;
  _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); }
} _;
int main() {
  int n, m, k, q;
  cin >> n >> m >> k >> q;
  vector<vector<int>> t(n, vector<int>(m, INT_MAX));
  for (int i = 1; i <= q; i++) {
    int x, y, tim;
    cin >> x >> y >> tim;
    t[x - 1][y - 1] = tim;
  }
  vector<vector<int>> t1(n, vector<int>(m - k + 1, INT_MAX));
  vector<multiset<int, greater<int>>> s(n);
  for (int en = 0; en <= k - 1; en++) {
    for (int i = 0; i <= n - 1; i++) s[i].insert(t[i][en]);
  }
  for (int i = 0; i <= n - 1; i++) t1[i][0] = *s[i].begin();
  for (int en = k, beg = 0; en <= m - 1; en++, beg++) {
    for (int i = 0; i <= n - 1; i++) {
      s[i].insert(t[i][en]);
      s[i].erase(s[i].find(t[i][beg]));
      t1[i][beg + 1] = *s[i].begin();
    }
  }
  vector<vector<int>> t2(n - k + 1, vector<int>(m - k + 1, INT_MAX));
  s.clear();
  s.resize(m - k + 1);
  for (int en = 0; en <= k - 1; en++) {
    for (int j = 0; j <= m - k; j++) s[j].insert(t1[en][j]);
  }
  for (int j = 0; j <= m - k; j++) t2[0][j] = *s[j].begin();
  for (int en = k, beg = 0; en <= n - 1; en++, beg++) {
    for (int j = 0; j <= m - k; j++) {
      s[j].insert(t1[en][j]);
      s[j].erase(s[j].find(t1[beg][j]));
      t2[beg + 1][j] = *s[j].begin();
    }
  }
  int ans = INT_MAX;
  for (auto i : t2)
    for (auto j : i) ans = min(ans, j);
  cout << ((ans == INT_MAX) ? -1 : ans);
  return 0;
}
