bool isit(multiset<ll> mse, ll mid, ll k, ll n) {
    ll req = n / 2;
    ll arrays = 0;
    ll sum = 0;
    while(arrays < n) {
        ll z = 0;
        while(z < req) {
            mse.erase(mse.begin());
            z ++;
        }
        if(*mse.rbegin() < mid) {
            break;
        }
        auto it = * mse.lower_bound(mid);
        mse.erase(mse.lower_bound(mid));
        sum += it;
        arrays ++;
    }
    return arrays >= n && sum <= k;
}
void solve() {
    ll n, k;
    cin >> n >> k;
    ll start = n/2, end = n * n - 1;
    ll ans = -1;
    vector<ll> tot;
    
    for(ll i = 0; i < n; i ++) {
        for(ll j = 0; j < n; j ++) {
            ll x; 
            cin >> x;
            tot.push_back(x);
        }
    }
    
    sov(tot); // sort vector
    multiset<ll> mse;
    ll t = ((n + 2) / 2) * n;
    for(int i = 0; i < t; i ++) {
        mse.insert(tot[i]);
    }
    
    start = n / 2;
    end = t - 1;
    
    while(start <= end) {
        ll mid = (start + end)/2;
        if(isit(mse, tot[mid], k, n)) {
            ans = tot[mid];
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    cout << ans << endl;
}

If each row is sorted, then the whole thing looks like this (S — some small values, M — row median values, B — some big values): ~~~~~ S1 S2 M1 B1 S3 S4 M2 B2 S5 S6 M3 B3 ~~~~~ With infinite $$$K$$$, the optimal median can be found in the following way. We can sort all values. Then the biggest values are assigned to B. The biggest among the remaining values are assigned to M. And S values are whatever is left. So that $$$S_x <= M_y <= B_z$$$ for any x, y, z.

Now if we want to also consider $$$K$$$, then we can safely throw away $$$B_z$$$ and look only at the combined set of $$$S_x$$$ and $$$M_y$$$ values. The problem is reduced to constructing a matrix, where each row is sorted and the sum of the largest values from each row does not exceed K.

As an example, let's look at sorted list of values [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15] from the testcase 2 (the largest values [16, 17, 24, 32] are thrown away). And then a recursive greedy algorithm checks the following arrangements, using a prefix sum array to calculate cost in constant time:

• [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 9+11+13+15 = the maximal possible cost
• [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 9+9+11+15
• [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 8+9+9+15
• [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 6+8+9+15 <= K (found the solution!)
• [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 5+6+9+15
• [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 3+6+9+15
• [1, 2, 3, 3, 5, 6, 8, 9, 9, 11, 13, 15], cost = 3+6+9+15 = the minimal possible cost

The rearranged matrix looks like this (6, 8, 9, 15 are on the median, the thrown away values 16, 17, 24, 32 are appended to the right): ~~~~~ 1, 2, 6, 16 3, 3, 8, 17 5, 9, 9, 24 11, 13, 15, 32 ~~~~~

A link to my submission: https://www.codechef.com/viewsolution/53224037