#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const long long SIZE = 505;
const long long mod = 1e9 + 7;
long long mon[SIZE][SIZE];
long long n, m, k, in;
long long col[SIZE][SIZE * 4];
long long row[SIZE][SIZE * 4];
void build_col(long long node, long long r1, long long r2) {
  if (r1 == r2) {
    col[in][node] = mon[r1][in];
    return;
  }
  long long bam = node * 2;
  long long dan = bam + 1;
  long long mid = (r1 + r2) / 2;
  build_col(bam, r1, mid);
  build_col(dan, mid + 1, r2);
  col[in][node] = max(col[in][bam], col[in][dan]);
}
long long query_col(long long node, long long r1, long long r2, long long i,
                    long long j) {
  long long bam = node * 2;
  long long dan = bam + 1;
  if (r1 > j || r2 < i) return -INF;
  if (r1 >= i && r2 <= j) return col[in][node];
  long long mid = (r1 + r2) / 2;
  long long p1 = query_col(bam, r1, mid, i, j);
  long long p2 = query_col(dan, mid + 1, r2, i, j);
  return max(p1, p2);
}
void build_row(long long node, long long r1, long long r2) {
  if (r1 == r2) {
    row[in][node] = mon[in][r1];
    return;
  }
  long long bam = node * 2;
  long long dan = bam + 1;
  long long mid = (r1 + r2) / 2;
  build_row(bam, r1, mid);
  build_row(dan, mid + 1, r2);
  row[in][node] = max(row[in][bam], row[in][dan]);
}
long long query_row(long long node, long long r1, long long r2, long long i,
                    long long j) {
  long long bam = node * 2;
  long long dan = bam + 1;
  if (r1 > j || r2 < i) return -INF;
  if (r1 >= i && r2 <= j) return row[in][node];
  long long mid = (r1 + r2) / 2;
  long long p1 = query_row(bam, r1, mid, i, j);
  long long p2 = query_row(dan, mid + 1, r2, i, j);
  return max(p1, p2);
}
int main() {
  long long t = 0, x, y, z, i, j, g, p, q, ans = INF, sum = 0, c = 0;
  string s, s1, s2;
  scanf("%lld %lld", &n, &m);
  scanf("%lld %lld", &k, &q);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) mon[i][j] = INF;
  while (q--) {
    scanf("%lld %lld %lld", &x, &y, &t);
    mon[x][y] = t;
  }
  for (i = 1; i <= m; i++) {
    in = i;
    build_col(1, 1, n);
  }
  for (j = 1; j <= m; j++) {
    in = j;
    for (i = k; i <= n; i++) {
      t = query_col(1, 1, n, i - k + 1, i);
      mon[i][j] = t;
    }
  }
  for (i = 1; i <= n; i++) {
    in = i;
    build_row(1, 1, m);
  }
  for (i = k; i <= n; i++) {
    in = i;
    for (j = k; j <= m; j++) {
      t = query_row(1, 1, m, j - k + 1, j);
      if (t != INF) ans = min(ans, t);
    }
  }
  if (ans == INF)
    printf("-1\n");
  else
    printf("%lld\n", ans);
  return 0;
}
