#include <bits/stdc++.h>
using namespace std;
template <typename T>
void inpos(T &x) {
  x = 0;
  register T c = getchar();
  while (((c < 48) || (c > 57)) && (c != '-')) c = getchar();
  bool neg = false;
  if (c == '-') neg = true;
  for (; c < 48 || c > 57; c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) x = (x << 3) + (x << 1) + (c & 15);
  if (neg) x = -x;
}
const int MAX = 505;
int n, m, k, q;
int a[MAX][MAX];
int qu[MAX * MAX][3];
bool solve(int mid) {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      a[i][j] = 0;
    }
  }
  for (int i = 1; i <= q; ++i) {
    if (qu[i][3] <= mid) {
      a[qu[i][1]][qu[i][2]] = 1;
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 2; j <= m; ++j) {
      a[i][j] += a[i][j - 1];
    }
  }
  for (int j = 1; j <= m; ++j) {
    for (int i = 2; i <= n; ++i) {
      a[i][j] += a[i - 1][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      int l = i + k - 1;
      int r = j + k - 1;
      if (l > n || j > m) {
        break;
      }
      int sum = a[l][r] + a[i - 1][j - 1];
      sum -= a[i - 1][r] + a[l][j - 1];
      if (sum == k * k) {
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  inpos(n), inpos(m), inpos(k), inpos(q);
  for (int i = 1; i <= q; ++i) {
    inpos(qu[i][1]);
    inpos(qu[i][2]);
    inpos(qu[i][3]);
  }
  long long low = 0, high = 2e9, ans = high;
  while (low <= high) {
    long long mid = (low + high) / 2;
    if (solve(mid)) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  if (ans == (int)2e9) {
    ans = -1;
  }
  printf("%lld\n", ans);
  return 0;
}
