#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #if __has_include() #include using namespace atcoder; #endif #include #include using namespace std; using namespace chrono; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; using mint = modint998244353; using MINT = modint1000000007; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; constexpr double pi = 3.141592653589793; constexpr ll smallMOD = 998244353; constexpr ll bigMOD = 1000000007; constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(15); } } init; template ostream &operator<<(ostream &os, const vector &vec) { os << "["; rep(i, vec.size()) { os << vec[i]; if (i != vec.size() - 1) os << ", "; } os << "]"; return os; } template ostream &operator<<(ostream &os, const vector> &vec) { os << "["; rep(i, vec.size()) { os << vec[i]; if (i != vec.size() - 1) os << ", "; } os << "]"; return os; } // graph_template struct Edge { ll to; ll cost; Edge(ll to, ll cost) : to(to), cost(cost) {} bool operator>(const Edge &e) const { return cost > e.cost; } }; int main() { ll n, m, k; cin >> n >> m >> k; vector> mp(n, vector(m, 0)); rep(i, n) { rep(j, m) { cin >> mp[i][j]; } } // 右にm個、下にn個移動したときのパス. vector>> dp(n, vector>(m, vector())); dp[0][0] = {mp[0][0]}; rep1(i, n - 1) { vector tmp = dp[i - 1][0]; tmp.push_back(mp[i][0]); sort(all(tmp)); dp[i][0] = tmp; } rep1(j, m - 1) { vector tmp = dp[0][j - 1]; tmp.push_back(mp[0][j]); sort(all(tmp)); dp[0][j] = tmp; } rep(i, n) { rep(j, m) { if (i == 0 || j == 0) continue; vector tmp1 = dp[i - 1][j]; vector tmp2 = dp[i][j - 1]; ll addNum = mp[i][j]; tmp1.push_back(addNum); tmp2.push_back(addNum); sort(all(tmp1)); sort(all(tmp2)); ll t1 = 1e9, t2 = 1e9; rep(i, tmp1.size()) { if (i < k) break; t1 = min(t1, tmp1[i]); t2 = min(t2, tmp2[i]); } if (t1 > t2) { dp[i][j] = tmp1; } else { dp[i][j] = tmp2; } } } vector last = dp[n - 1][m - 1]; sort(all(last)); rep(i, k) { if (i >= last.size()) break; last[i] = 1e9; } cout << *min_element(all(last)) << endl; return 0; }