#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const double EPS = 1e-9;
const int INF = 1 << 29;
int const NN = 5e3 + 3;
int const MX = 1e9 + 9;
int a[505][505];
int mx[505][505];
int main() {
  int n, m, K, q;
  cin >> n >> m >> K >> q;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) a[i][j] = MX;
  }
  while (q--) {
    int x, y, t;
    cin >> x >> y >> t;
    a[x][y] = t;
  }
  int ans = MX;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      mx[i][j] = a[i][j];
      for (int k = 2; i + k - 1 <= n && k <= K; ++k) {
        mx[i][j] = max(mx[i][j], a[i + k - 1][j]);
      }
    }
  }
  for (int i = 1; i + K - 1 <= n; ++i) {
    for (int j = 1; j + K - 1 <= m; ++j) {
      int mxx = -1;
      for (int jj = j; jj <= j + K - 1; ++jj) {
        mxx = max(mxx, mx[i][jj]);
      }
      ans = min(ans, mxx);
    }
  }
  if (ans < MX) {
    printf("%d", ans);
    ;
    putchar('\n');
  } else
    puts("-1");
  return 0;
}
