#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long max3(long long a, long long b, long long c) {
  return max(max(a, b), c);
}
long long max4(long long a, long long b, long long c, long long d) {
  return max(max(a, b), max(c, d));
}
long long min3(long long a, long long b, long long c) {
  return min(min(a, b), c);
}
long long min4(long long a, long long b, long long c, long long d) {
  return min(min(a, b), min(c, d));
}
long long po(long long x, long long n, long long mod = 1000000007) {
  if (n == 0) {
    return 1;
  }
  long long m = po(x, n / 2, mod);
  m *= m;
  m %= mod;
  if (n % 2) {
    m *= x;
    m %= mod;
  }
  return m;
}
bool comp(pair<pair<long long, long long>, long long> p1,
          pair<pair<long long, long long>, long long> p2) {
  return p1.second < p2.second;
}
long long n, m, k, q;
vector<pair<pair<long long, long long>, long long>> v;
bool check(long long x) {
  long long pix[505][505] = {}, dp[505][505] = {};
  for (long long i = 0; i < v.size(); i++) {
    if (v[i].second > x) {
      continue;
    }
    pix[v[i].first.first][v[i].first.second] = 1;
  }
  for (long long i = 1; i < 505; i++) {
    if (pix[1][i]) {
      dp[1][i] = 1;
    }
    if (pix[i][1]) {
      dp[i][1] = 1;
    }
    if (dp[1][i] >= k) {
      return 1;
    }
    if (dp[i][1] >= k) {
      return 1;
    }
  }
  for (long long i = 2; i < 505; i++) {
    for (long long j = 2; j < 505; j++) {
      if (pix[i][j]) {
        dp[i][j] = min3(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
      if (dp[i][j] >= k) {
        return 1;
      }
    }
  }
  return 0;
}
int32_t main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  clock_t startTime = clock();
  cout << fixed << setprecision(12);
  cin >> n >> m >> k >> q;
  for (long long i = 0; i < q; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    v.push_back({{a, b}, c});
  }
  sort((v).begin(), (v).end(), comp);
  long long left = 0, right = 1e9 + 5;
  if (!check(right)) {
    cout << -1;
    return 0;
  }
  while (left < right) {
    long long mid = (left + right) / 2;
    if (check(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
    if (left == right - 1) {
      break;
    }
  }
  if (left == right) {
    cout << left;
    return 0;
  }
  if (check(left)) {
    cout << left;
  } else {
    cout << right;
  }
}
