大きい方から \(K\) 番目の整数を固定し、その値を \(X\) とします。

DP を用いて、\(X\) 以上の整数が書かれたマスを \(k\) 個通った時の \(X\) 以上の整数の和の最小値を各マスについて管理します。

\(1\) 回の DP の計算量は \(O(HWK)\) なので、全体の計算量は \(O(H^2W^2K)\) です。

\(X\) の書かれたマスが複数ある場合の処理に注意してください。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; i++)
void chmin(ll&a,ll b){if(a>b)a=b;}
const ll inf = 1001001001001001001;

int main(){
    int h, w, K; cin >> h >> w >> K;
    vector<vector<int>> grid(h, vector<int>(w));
    rep(i, h) rep(j, w) cin >> grid[i][j];
    ll ans = inf;
    for(auto y : grid) for(auto x : y) {
        vector<vector<vector<ll>>> dp(K + 1, vector<vector<ll>>(h, vector<ll>(w, inf)));
        if(grid[0][0] >= x) dp[1][0][0] = grid[0][0];
        if(grid[0][0] <= x) dp[0][0][0] = 0;
        rep(i, K + 1) rep(j, h) rep(k, w) {
            if(j != h - 1){
                if(i != K && grid[j + 1][k] >= x) chmin(dp[i + 1][j + 1][k], dp[i][j][k] + grid[j + 1][k]);
                if(grid[j + 1][k] <= x) chmin(dp[i][j + 1][k], dp[i][j][k]);
            }
            if(k != w - 1){
                if(i != K && grid[j][k + 1] >= x) chmin(dp[i + 1][j][k + 1], dp[i][j][k] + grid[j][k + 1]);
                if(grid[j][k + 1] <= x) chmin(dp[i][j][k + 1], dp[i][j][k]);
            }
        }
        chmin(ans, dp[K][h - 1][w - 1]);
    }
    cout << ans << endl;
}

bonus: \(O(H^2W^2)\)