#include <bits/stdc++.h>
using namespace std;
auto scan = [] {
  static long long a;
  scanf("%lld", &a);
  return a;
};
pair<long long, pair<long long, long long> > broke[500 * 500];
long long board[500][500], n, m, k, q, x, y, t;
void printboard(long long n, long long m) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      printf("%lld%c", board[i][j], " \n"[j == m - 1]);
    }
  puts("");
}
bool tryit(long long t) {
  memset(board, 0ll, sizeof(board));
  for (int i = 0; i < t; ++i)
    board[broke[i].second.first][broke[i].second.second] = 1;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      board[i][j] += (i ? board[i - 1][j] : 0) + (j ? board[i][j - 1] : 0) -
                     (i && j ? board[i - 1][j - 1] : 0);
  for (int i = k; i < n + 1; ++i)
    for (int j = k; j < m + 1; ++j) {
      long long cur = board[i - 1][j - 1] -
                      ((i - k) ? board[i - k - 1][j - 1] : 0) -
                      ((j - k) ? board[i - 1][j - k - 1] : 0) +
                      ((i - k) && (j - k) ? board[i - k - 1][j - k - 1] : 0);
      if (cur >= k * k) return true;
    }
  return false;
}
int main() {
  n = scan(), m = scan(), k = scan(), q = scan();
  for (int i = 0; i < q; ++i) {
    x = scan(), y = scan(), t = scan();
    broke[i] = {t, {x - 1, y - 1}};
  }
  sort(broke, broke + q);
  long long l = 0, r = q, mid;
  while (l < r - 1) {
    mid = (l + r) / 2;
    (tryit(mid) ? r : l) = mid;
  }
  if (tryit(r))
    printf("%lld\n", broke[r - 1].first);
  else
    puts("-1");
}
