#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
int a[510][510];
int mi[510][510];
int main() {
  ios_base::sync_with_stdio(0);
  int n, m, k, q;
  cin >> n >> m >> k >> q;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      a[i][j] = -1;
      mi[i][j] = -1;
    }
  for (int i = 1; i <= q; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    a[x][y] = z;
  }
  for (int i = 1; i <= n; i++) {
    multiset<int> st;
    for (int j = 1; j <= k; j++) {
      st.insert(a[i][j]);
    }
    for (int j = k + 1; j <= m + 1; j++) {
      auto kk = st.end();
      kk--;
      if ((*st.begin()) != -1) mi[i][j - k] = (*kk);
      st.erase(st.find(a[i][j - k]));
      st.insert(a[i][j]);
    }
  }
  int ans = 2e9;
  for (int j = 1; j <= m - k + 1; j++) {
    multiset<int> st;
    for (int i = 1; i <= k; i++) {
      st.insert(mi[i][j]);
    }
    for (int i = k + 1; i <= n + 1; i++) {
      auto kk = st.end();
      kk--;
      if ((*st.begin()) != -1) ans = min(ans, (*kk));
      st.erase(st.find(mi[i - k][j]));
      st.insert(mi[i][j]);
    }
  }
  if (ans == 2e9)
    cout << -1;
  else
    cout << ans;
}
