#include <bits/stdc++.h>
using namespace std;
int maxv[510 << 2][510 << 2], rt;
bool isleaf;
int n, m, q, k;
struct TWO_D_SegmentTree {
  struct SegmentTree {
    struct node {
      short l, r;
    } tree[510 << 2];
    short l, r;
    inline void push_up(int i) {
      maxv[rt][i] = max(maxv[rt][i << 1], maxv[rt][i << 1 | 1]);
    }
    inline void build(int i, int l, int r) {
      tree[i].r = r;
      tree[i].l = l;
      if (l == r) {
        if (isleaf)
          maxv[rt][i] = 0x3f3f3f3f;
        else
          maxv[rt][i] = max(maxv[rt << 1][i], maxv[rt << 1 | 1][i]);
        return;
      }
      int mid = (l + r) >> 1;
      build(i << 1, l, mid);
      build(i << 1 | 1, mid + 1, r);
      push_up(i);
    }
    inline void modify(int i, int l, int r, int x) {
      if ((tree[i].l == l) && (tree[i].r == r)) {
        if (isleaf) maxv[rt][i] = x;
        if (!isleaf) maxv[rt][i] = max(maxv[rt << 1][i], maxv[rt << 1 | 1][i]);
        return;
      }
      int mid = (tree[i].l + tree[i].r) >> 1;
      if (mid >= r)
        modify(i << 1, l, r, x);
      else if (mid < l)
        modify(i << 1 | 1, l, r, x);
      else {
        modify(i << 1, l, mid, x);
        modify(i << 1 | 1, mid + 1, r, x);
      }
      push_up(i);
    }
    inline int getmax(int i, int l, int r) {
      if ((tree[i].l == l) && (tree[i].r == r)) return maxv[rt][i];
      int mid = (tree[i].l + tree[i].r) >> 1;
      if (mid >= r)
        return getmax(i << 1, l, r);
      else if (mid < l)
        return getmax(i << 1 | 1, l, r);
      else
        return max(getmax(i << 1, l, mid), getmax(i << 1 | 1, mid + 1, r));
    }
  } seg[510 << 2];
  inline void build(int i, int l, int r) {
    seg[i].r = r;
    seg[i].l = l;
    if (l == r) {
      rt = i;
      isleaf = 1;
      seg[i].build(1, 1, m);
      return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    rt = i;
    isleaf = 0;
    seg[i].build(1, 1, m);
  }
  inline void modify(int i, int x1, int y1, int x2, int y2, int x) {
    if ((seg[i].l == x1) && (seg[i].r == x2)) {
      rt = i;
      isleaf = 1;
      seg[i].modify(1, y1, y2, x);
      return;
    }
    int mid = (seg[i].l + seg[i].r) >> 1;
    if (mid >= x2)
      modify(i << 1, x1, y1, x2, y2, x);
    else if (mid < x1)
      modify(i << 1 | 1, x1, y1, x2, y2, x);
    else {
      modify(i << 1, x1, y1, mid, y2, x);
      modify(i << 1 | 1, mid + 1, y1, x2, y2, x);
    }
    rt = i;
    isleaf = 0;
    seg[i].modify(1, y1, y2, x);
  }
  inline int getmax(int i, int x1, int y1, int x2, int y2) {
    if ((seg[i].l == x1) && (seg[i].r == x2)) {
      rt = i;
      return seg[i].getmax(1, y1, y2);
    }
    int mid = (seg[i].l + seg[i].r) >> 1;
    if (mid >= x2)
      return getmax(i << 1, x1, y1, x2, y2);
    else if (mid < x1)
      return getmax(i << 1 | 1, x1, y1, x2, y2);
    else
      return max(getmax(i << 1, x1, y1, mid, y2),
                 getmax(i << 1 | 1, mid + 1, y1, x2, y2));
  }
} two_d_seg;
int main() {
  scanf("%d%d%d%d", &n, &m, &k, &q);
  two_d_seg.build(1, 1, n);
  for (int i = 1; i <= q; i++) {
    int x, y, t;
    scanf("%d%d%d", &x, &y, &t);
    two_d_seg.modify(1, x, y, x, y, t);
  }
  int ans = 0x3f3f3f3f;
  for (int i = 1; i <= n - k + 1; i++)
    for (int j = 1; j <= m - k + 1; j++)
      ans = min(ans, two_d_seg.getmax(1, i, j, i + k - 1, j + k - 1));
  if (ans == 0x3f3f3f3f)
    puts("-1");
  else
    printf("%d\n", ans);
  return 0;
}
