#include <bits/stdc++.h>
using namespace std;
int a[501][501];
int dp[501][501];
int n, m, k, q;
bool check(int mid) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) dp[i][j] = (a[i][j] != -1 && a[i][j] <= mid);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + dp[i][j];
  for (int i = k; i <= n; i++)
    for (int j = k; j <= m; j++) {
      if (dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k] == k * k)
        return 1;
    }
  return 0;
}
int main() {
  scanf("%d %d %d %d", &n, &m, &k, &q);
  int l = 0;
  int r = (int)(1e9);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) a[i][j] = -1;
  while (q--) {
    int x, y, time;
    scanf("%d %d %d", &x, &y, &time);
    a[x][y] = time;
    r = max(r, time);
    l = min(l, time);
  }
  int ans = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      ans = (ans == -1 ? mid : min(ans, mid));
      r = mid - 1;
    } else
      l = mid + 1;
  }
  printf("%d", ans);
}
