#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 1;
const int mod = 1e9 + 7;
inline int read() {
  char c = getchar();
  int t = 0, f = 1;
  while (!isdigit(c)) f = (c == '-') ? -1 : 1, c = getchar();
  while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * f;
}
int a[510][510];
int b[510][510];
int sum[510][510];
int n, m, k, q;
int logn[N], dp[20][N];
int get_max(int l, int r) {
  int len = r - l + 1;
  return max(dp[logn[len]][l], dp[logn[len]][r - (1 << logn[len]) + 1]);
}
int Max(int x1, int y1, int x2, int y2) {
  int mx = 0;
  for (int i = x1; i <= x2; i++)
    mx = max(mx, get_max((i - 1) * m + y1, (i - 1) * m + y2));
  return mx;
}
int main() {
  logn[1] = 0;
  for (int i = 2; i <= 2e5; i++) logn[i] = logn[i / 2] + 1;
  n = read(), m = read(), k = read(), q = read();
  for (int i = 1; i <= q; i++) {
    int x = read(), y = read();
    a[x][y] = read();
    b[x][y] = 1;
  }
  for (int i = 1; i <= n * m; i++)
    dp[0][i] = a[(i + m - 1) / m][i % m ? i % m : m];
  for (int k = 1; k <= 20; k++) {
    int len = (1 << k);
    for (int j = 1; j + len - 1 <= n * m; j++) {
      dp[k][j] = max(dp[k - 1][j], dp[k - 1][j + len / 2]);
    }
  }
  for (int i = 1; i <= n; i++) {
    int s = 0;
    for (int j = 1; j <= m; j++) {
      s += b[i][j];
      sum[i][j] = sum[i - 1][j] + s;
    }
  }
  int ans = 2e9;
  for (int i = 1; i <= n - k + 1; i++) {
    for (int j = 1; j <= m - k + 1; j++) {
      int s = sum[i + k - 1][j + k - 1] - sum[i - 1][j + k - 1] -
              sum[i + k - 1][j - 1] + sum[i - 1][j - 1];
      if (s == k * k) {
        ans = min(ans, Max(i, j, i + k - 1, j + k - 1));
      }
    }
  }
  cout << (ans == 2e9 ? -1 : ans);
}
