#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int grid[N][N], n, m, k, q;
long long Pre[N][N];
vector<pair<int, pair<int, int>>> vv;
inline bool Ok(int mid) {
  memset(Pre, 0, sizeof(Pre));
  int indx = 0;
  while (indx < q && vv[indx].first <= mid) {
    Pre[vv[indx].second.first][vv[indx].second.second] = 1;
    indx++;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      Pre[i][j] += Pre[i - 1][j] + Pre[i][j - 1] - Pre[i - 1][j - 1];
  for (int i = 1; i + k - 1 <= n; ++i)
    for (int j = 1, x2, y2; k + j - 1 <= m; ++j) {
      x2 = i + k - 1;
      y2 = j + k - 1;
      if (Pre[x2][y2] - Pre[x2][j - 1] - Pre[i - 1][y2] + Pre[i - 1][j - 1] ==
          k * k)
        return 1;
    }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.precision(10), cout << fixed;
  cin >> n >> m >> k >> q;
  for (int i = 0, x, y, t; i < q; ++i) {
    cin >> x >> y >> t;
    vv.push_back({t, {x, y}});
  }
  sort(vv.begin(), vv.end());
  int ans = -1;
  int low = 0, high = 1e9 + 9;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (Ok(mid)) {
      ans = mid;
      high = mid - 1;
    } else
      low = mid + 1;
  }
  cout << ans << '\n';
  return 0;
}
