#include <bits/stdc++.h>
using namespace std;
const int nMax = 505;
const int mMax = 505;
const int INF = 2000000000;
int n, m, k, q;
int a[nMax][mMax];
int lineMax[nMax][mMax];
int matrixMax[nMax][mMax];
int main() {
  cin >> n >> m >> k >> q;
  int x, y, t;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) a[i][j] = INF;
  for (int i = 1; i <= q; ++i) {
    cin >> x >> y >> t;
    a[x][y] = t;
  }
  for (int i = 1; i <= n; ++i) {
    deque<int> dq;
    for (int j = 1; j <= m; ++j) {
      while (dq.empty() == false && a[i][dq.back()] <= a[i][j]) dq.pop_back();
      dq.push_back(j);
      if (j - dq.front() + 1 > k) dq.pop_front();
      lineMax[i][j] = a[i][dq.front()];
    }
  }
  for (int j = 1; j <= m; ++j) {
    deque<int> dq;
    for (int i = 1; i <= n; ++i) {
      while (dq.empty() == false && lineMax[dq.back()][j] <= lineMax[i][j])
        dq.pop_back();
      dq.push_back(i);
      if (i - dq.front() + 1 > k) dq.pop_front();
      matrixMax[i][j] = lineMax[dq.front()][j];
    }
  }
  int ans = INF;
  for (int i = k; i <= n; ++i)
    for (int j = k; j <= m; ++j) ans = min(ans, matrixMax[i][j]);
  if (ans == INF)
    cout << -1;
  else
    cout << ans;
  return 0;
}
