#include <bits/stdc++.h>
using namespace std;
const long double PI = atan(1.0) * 4.0;
const long long int MOD = 1e9 + 7;
const long long int INF = 1e18;
const long double EPS = 0.0000001;
long long int n, m, k, q, arr[505][505], colKMax[505][505], x, y,
    rowColKMax[505][505];
void KMax(int col) {
  deque<int> Qi(k);
  int i;
  int row = 0;
  for (i = 0; i < k; ++i) {
    while ((!Qi.empty()) && arr[i][col] >= arr[Qi.back()][col]) Qi.pop_back();
    Qi.push_back(i);
  }
  for (; i < n; ++i) {
    colKMax[row++][col] = arr[Qi.front()][col];
    while ((!Qi.empty()) && Qi.front() <= i - k) Qi.pop_front();
    while ((!Qi.empty()) && arr[i][col] >= arr[Qi.back()][col]) Qi.pop_back();
    Qi.push_back(i);
  }
  colKMax[row++][col] = arr[Qi.front()][col];
}
void KMax2(int row) {
  deque<int> Qi(k);
  int i;
  int col = 0;
  for (i = 0; i < k; ++i) {
    while ((!Qi.empty()) && colKMax[row][i] >= colKMax[row][Qi.back()])
      Qi.pop_back();
    Qi.push_back(i);
  }
  for (; i < m; ++i) {
    rowColKMax[row][col++] = colKMax[row][Qi.front()];
    while ((!Qi.empty()) && Qi.front() <= i - k) Qi.pop_front();
    while ((!Qi.empty()) && colKMax[row][i] >= colKMax[row][Qi.back()])
      Qi.pop_back();
    Qi.push_back(i);
  }
  rowColKMax[row][col++] = colKMax[row][Qi.front()];
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  cin >> n >> m >> k >> q;
  fill(&arr[0][0], &arr[505 - 1][505 - 1], INF);
  for (int i = 0; i <= q - 1; i++) {
    cin >> x >> y;
    x--;
    y--;
    cin >> arr[x][y];
  }
  for (int i = 0; i <= m - 1; i++) KMax(i);
  for (int i = 0; i <= n - k; i++) KMax2(i);
  long long int ans = INF;
  for (int i = 0; i <= n - k; i++) {
    for (int j = 0; j <= m - k; j++) {
      ans = min(ans, rowColKMax[i][j]);
    }
  }
  if (ans == INF)
    cout << "-1" << endl;
  else
    cout << ans << endl;
  return 0;
}
