#include <bits/stdc++.h>
using namespace std;
int a[510][510] = {0}, d[510][510] = {0};
int main() {
  int m, n, k, q, x, y, t, i, j, l, r, result = -1, mid;
  cin >> n >> m >> k >> q;
  memset(a, 63, sizeof(a));
  for (i = 1; i <= q; i++) {
    scanf("%d%d%d", &x, &y, &t);
    a[x][y] = t;
  }
  l = 0;
  r = 1000000000;
  while (l <= r) {
    mid = (l + r) / 2;
    bool nico = 0;
    memset(d, 0, sizeof(d));
    for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++) {
        d[i][j] = 1 + min(d[i - 1][j - 1], min(d[i][j - 1], d[i - 1][j]));
        if (a[i][j] > mid) d[i][j] = 0;
        if (d[i][j] >= k) nico = 1;
      }
    if (nico == 1) {
      result = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  cout << result;
}
