#include <bits/stdc++.h>
using namespace std;
struct pixel {
  int x, y, t;
};
vector<pixel> v;
int n, m, k, arr[505][505], pre[505][505], row[505];
bool compare(pixel &A, pixel &B) { return A.t < B.t; }
bool ok(int x) {
  memset(arr, 0, sizeof(arr));
  int i, j;
  for (i = 0; i < x; i++) arr[v[i].x - 1][v[i].y - 1] = 1;
  for (i = 0; i < n; i++) {
    for (j = 0; j < m; j++) {
      if (j == 0) {
        if (i == 0)
          pre[i][j] = arr[i][j];
        else
          pre[i][j] = pre[i - 1][j] + arr[i][j];
        row[j] = arr[i][j];
      } else {
        if (i)
          pre[i][j] = pre[i - 1][j] + row[j - 1] + arr[i][j];
        else
          pre[i][j] = row[j - 1] + arr[i][j];
        row[j] = row[j - 1] + arr[i][j];
      }
    }
  }
  for (i = 0; i + k <= n; i++) {
    for (j = 0; j + k <= m; j++) {
      if (i == 0) {
        if (j == 0) {
          if (pre[i + k - 1][j + k - 1] == k * k) return true;
        } else {
          if (pre[i + k - 1][j + k - 1] - pre[i + k - 1][j - 1] == k * k)
            return true;
        }
      } else if (j == 0) {
        if (pre[i + k - 1][j + k - 1] - pre[i - 1][j + k - 1] == k * k)
          return true;
      } else {
        if (pre[i + k - 1][j + k - 1] - pre[i + k - 1][j - 1] -
                pre[i - 1][j + k - 1] + pre[i - 1][j - 1] ==
            k * k)
          return true;
      }
    }
  }
  return false;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q, i, lo, hi, mid, ans = -1;
  cin >> n >> m >> k >> q;
  while (q--) {
    pixel cur;
    cin >> cur.x >> cur.y >> cur.t;
    v.push_back(cur);
  }
  sort(v.begin(), v.end(), compare);
  lo = 1;
  hi = v.size();
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (ok(mid)) {
      ans = v[mid - 1].t;
      hi = mid - 1;
    } else
      lo = mid + 1;
  }
  cout << ans << '\n';
  return 0;
}
