#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, k, q;
int vis[N][N];
struct node {
  int x, y, t;
} p[300000];
bool check(int mid) {
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= q; ++i)
    if (p[i].t <= mid) vis[p[i].x][p[i].y] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      vis[i][j] += vis[i - 1][j] + vis[i][j - 1] - vis[i - 1][j - 1];
      if (i >= k && j >= k &&
          vis[i][j] - vis[i - k][j] - vis[i][j - k] + vis[i - k][j - k] ==
              k * k)
        return 1;
    }
  return 0;
}
int main(void) {
  while (~scanf("%d%d%d%d", &n, &m, &k, &q)) {
    int Max = 0;
    for (int i = 1; i <= q; i++) {
      scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].t);
      if (p[i].t > Max) Max = p[i].t;
    }
    int l = -1, r = Max + 1, ans = 0x3f3f3f3f;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
  }
}
