#include using namespace std; #define int long long int N,M,K; int INF = 1e18; int dx[4] = {1,0,0,-1}; int dy[4] = {0,1,-1,0}; signed main(){ cin>>N>>M>>K; vector> A(N,vector(M)); for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) cin>>A[i][j]; int ok = 0; int ng = INF; while(abs(ok - ng) > 1){ int mid = (ok + ng) / 2; deque> Q; vector> dist(N,vector(M,INF)); dist[0][0] = (A[0][0] < mid); Q.push_front({0,0}); while(!Q.empty()){ int nowi = Q.front().first; int nowj = Q.front().second; Q.pop_front(); for(int i = 0; i < 4; i++){ int nei = nowi + dx[i]; int nej = nowj + dy[i]; if(0 <= nei && nei < N && 0 <= nej && nej < M){ if(dist[nei][nej] > dist[nowi][nowj] + (A[nei][nej] < mid)){ dist[nei][nej] = dist[nowi][nowj] + (A[nei][nej] < mid); if(A[nei][nej] >= mid) Q.push_front({nei,nej}); else Q.push_back({nei,nej}); } } } if(dist[N-1][M-1] <= K) ok = mid; else ng = mid; } } cout << min(ok,1000000000ll) << "\n"; }