#include <bits/stdc++.h>
using namespace std;
int const INF = numeric_limits<int>::max();
long long const LLINF = numeric_limits<long long>::max();
long double const EPS = 1e-9;
int n, m, k, q;
int const N = 505;
int a[N][N];
struct qu {
  int x, y, t;
};
bool operator<(const qu& a, const qu& b) { return a.t < b.t; }
qu qq[N * N];
bool check() {
  int ans = 0;
  vector<int> d(m, -1), d1(m), d2(m);
  stack<int> st;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j)
      if (a[i][j] == 0) d[j] = i;
    while (!st.empty()) st.pop();
    for (int j = 0; j < m; ++j) {
      while (!st.empty() && d[st.top()] <= d[j]) st.pop();
      d1[j] = st.empty() ? -1 : st.top();
      st.push(j);
    }
    while (!st.empty()) st.pop();
    for (int j = m - 1; j >= 0; --j) {
      while (!st.empty() && d[st.top()] <= d[j]) st.pop();
      d2[j] = st.empty() ? m : st.top();
      st.push(j);
    }
    for (int j = 0; j < m; ++j)
      ans = max(ans, min((i - d[j]), (d2[j] - d1[j] - 1)));
  }
  return ans >= k;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> k >> q;
  for (int i = 0; i < q; i++) {
    cin >> qq[i].x >> qq[i].y >> qq[i].t;
    qq[i].x--;
    qq[i].y--;
    a[qq[i].x][qq[i].y] = 1;
  }
  if (!check()) {
    cout << -1 << endl;
    return 0;
  }
  sort(qq, qq + q);
  int l = 0, r = q - 1;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        a[i][j] = 0;
      }
    }
    for (int i = 0; i <= mid; i++) {
      a[qq[i].x][qq[i].y] = 1;
    }
    if (check()) {
      r = mid;
    } else {
      l = mid;
    }
  }
  while (r >= l) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        a[i][j] = 0;
      }
    }
    for (int i = 0; i <= l; i++) {
      a[qq[i].x][qq[i].y] = 1;
    }
    if (check()) {
      break;
    } else {
      l++;
    }
  }
  cout << qq[l].t << endl;
  return 0;
}
