1. Abridged problem statement  
Given an N×M grid of nonnegative weights and an integer K, pick exactly K cells so that  
- In each occupied row, the chosen cells form one contiguous segment [l,r].  
- For any two occupied rows, their segments overlap in at least one column.  
- Once the left boundary ever moves right you cannot later move it back left; similarly once the right boundary ever moves left you cannot later move it back right.  
These conditions guarantee that between any two chosen cells you can walk using at most two directions.  Maximize the total weight of the K selected cells.  Output the maximum sum and one valid set of K positions.

2. Detailed editorial  
We exploit the fact that any valid shape can be described by, for each row i, a segment [lᵢ, rᵢ], with  
  a) rᵢ ≥ lᵢ,  
  b) [lᵢ, rᵢ] ∩ [lᵢ₋₁, rᵢ₋₁] ≠ ∅ when both rows are used (so the shape is row‐connected),  
  c) the left endpoints {lᵢ} form a unimodal (never returning) sequence: once you shrink from the left (lᵢ > lᵢ₋₁), you may no longer expand to the left, and similarly for the right endpoints {rᵢ} forming a unimodal sequence on the other side.  

We set up a DP over rows with state  
  DP(row, l, r, rem, mask) = maximum extra oil obtainable from rows row…N−1,  
if in row−1 we used segment [l, r], we still need rem cells in total, and mask tells which sides have already “locked” (bit0=1 means left is locked, bit1=1 means right is locked).  

Transition: for the current row pick any new segment [l′, r′] that  
  1. has positive overlap with [l, r],  
  2. uses ≤ rem cells,  
  3. does not violate locked‐side constraints (i.e. if left side is unlocked you may move l′ ≤ l; if locked you must l′ ≥ l; similarly for r),  
  4. update new_mask by setting bit0 if you shrank from the left (l′ > l), bit1 if shrank from the right (r′ < r).  

We precompute 2D prefix sums so that the sum of any row‐segment is O(1).  The overall DP size is O(N·M²·K·4), and each transition loops over M², so about O(N·M⁴·K) ≲ 15·(15⁴)·225 ≃ 34M operations, which fits in time.  

Finally we take the best starting row and segment [l, r], run the DP to get the maximum sum, then retrace the choices to list all K cells.  

3. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int inf = (int)1e9 + 42;

int n, m, k;
vector<vector<int>> a;

void read() {
    cin >> n >> m >> k;
    a.resize(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
}

vector<vector<int>> psum;

int get_sum(int x1, int y1, int x2, int y2) {
    int res = psum[x2][y2];
    if(x1 > 0) {
        res -= psum[x1 - 1][y2];
    }
    if(y1 > 0) {
        res -= psum[x2][y1 - 1];
    }
    if(x1 > 0 && y1 > 0) {
        res += psum[x1 - 1][y1 - 1];
    }
    return res;
}

vector<vector<vector<vector<vector<int>>>>> dp;

int rec(int row, int l, int r, int cnt, int state) {
    if(row == n) {
        return (cnt == 0) ? 0 : -inf;
    }
    if(cnt == 0) {
        return 0;
    }

    int& memo = dp[row][l][r][cnt][state];
    if(memo != -1) {
        return memo;
    }

    bool can_move_l = (state & 1) == 0;
    bool can_move_r = (state & 2) == 0;

    memo = -inf;

    for(int new_l = 0; new_l <= m; new_l++) {
        for(int new_r = new_l; new_r < m; new_r++) {
            int overlap = min(r, new_r) - max(l, new_l) + 1;
            int new_cnt = cnt - (new_r - new_l + 1);
            if(new_cnt < 0) {
                continue;
            }

            if(overlap <= 0) {
                continue;
            }

            if(!can_move_l && new_l < l) {
                continue;
            }

            if(!can_move_r && new_r > r) {
                continue;
            }

            bool we_shrunk_left = new_l > l;
            bool we_shrunk_right = new_r < r;
            int new_state =
                state | (we_shrunk_left ? 1 : 0) | (we_shrunk_right ? 2 : 0);
            int sum = get_sum(row, new_l, row, new_r);
            memo =
                max(memo, sum + rec(row + 1, new_l, new_r, new_cnt, new_state));
        }
    }

    return memo;
}

void solve() {
    // A "convex" (row-monotone) region: each occupied row is a contiguous
    // segment [l, r], the left boundary first stays/moves right then the right
    // boundary stays/moves left, so the shape is monotone (no re-widening once
    // a side has shrunk). We DP over rows. The state is (row, l, r, cnt, mask)
    // where cnt is the remaining number of cells to place and the 2-bit mask
    // records whether the left/right boundary has already started shrinking
    // (once it has, that side may no longer expand). psum is a 2D prefix sum
    // for O(1) row-segment sums. rec returns the best oil achievable from the
    // given state; we try every starting row/segment, take the max, then
    // replay the same transitions matching the stored optimum to reconstruct
    // the chosen cells, finally printing them sorted.

    if(k == 0) {
        cout << "Oil : 0\n";
        return;
    }

    psum.assign(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            psum[i][j] = a[i][j];
            if(i > 0) {
                psum[i][j] += psum[i - 1][j];
            }
            if(j > 0) {
                psum[i][j] += psum[i][j - 1];
            }
            if(i > 0 && j > 0) {
                psum[i][j] -= psum[i - 1][j - 1];
            }
        }
    }

    dp.assign(
        n, vector<vector<vector<vector<int>>>>(
               m, vector<vector<vector<int>>>(
                      m, vector<vector<int>>(k + 1, vector<int>(4, -1))
                  )
           )
    );

    int ans = -inf;
    int start_row = -1, start_l = -1, start_r = -1;
    for(int row = 0; row < n; row++) {
        for(int l = 0; l < m; l++) {
            for(int r = l; r < m; r++) {
                int cnt = k - (r - l + 1);
                if(cnt >= 0) {
                    int sum = get_sum(row, l, row, r);
                    int res = sum + rec(row + 1, l, r, cnt, 0);
                    if(res > ans) {
                        ans = res;
                        start_l = l;
                        start_r = r;
                        start_row = row;
                    }
                }
            }
        }
    }

    cout << "Oil : " << ans << '\n';

    vector<pair<int, int>> cells;
    for(int i = start_l; i <= start_r; i++) {
        cells.emplace_back(start_row, i);
    }

    k -= (start_r - start_l + 1);
    ans -= get_sum(start_row, start_l, start_row, start_r);
    int state = 0;
    start_row++;
    while(k > 0) {
        int best_next_l = -1, best_next_r = -1, best_next_state = -1;
        bool can_move_l = (state & 1) == 0;
        bool can_move_r = (state & 2) == 0;
        for(int new_l = 0; new_l < m; new_l++) {
            for(int new_r = new_l; new_r < m; new_r++) {
                int overlap = min(start_r, new_r) - max(start_l, new_l) + 1;
                int new_cnt = k - (new_r - new_l + 1);
                if(new_cnt < 0) {
                    continue;
                }
                if(overlap <= 0) {
                    continue;
                }

                if(!can_move_l && new_l < start_l) {
                    continue;
                }

                if(!can_move_r && new_r > start_r) {
                    continue;
                }

                bool we_shrunk_left = new_l > start_l;
                bool we_shrunk_right = new_r < start_r;
                int new_state = state | (we_shrunk_left ? 1 : 0) |
                                (we_shrunk_right ? 2 : 0);
                int sum = get_sum(start_row, new_l, start_row, new_r);
                int next_res =
                    sum + rec(start_row + 1, new_l, new_r, new_cnt, new_state);
                if(next_res == ans) {
                    best_next_l = new_l;
                    best_next_r = new_r;
                    best_next_state = new_state;
                }
            }
        }

        assert(best_next_l != -1 && best_next_r != -1 && best_next_state != -1);

        for(int i = best_next_l; i <= best_next_r; i++) {
            cells.emplace_back(start_row, i);
        }

        ans -= get_sum(start_row, best_next_l, start_row, best_next_r);
        k -= (best_next_r - best_next_l + 1);
        start_row++;
        start_l = best_next_l;
        start_r = best_next_r;
        state = best_next_state;
    }

    sort(cells.begin(), cells.end());
    for(int i = 0; i < (int)cells.size(); i++) {
        cout << cells[i].first + 1 << ' ' << cells[i].second + 1 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python solution with detailed comments  
```python
import sys
sys.setrecursionlimit(10**7)
def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n, m, K = map(int, (next(it), next(it), next(it)))
    a = [[int(next(it)) for _ in range(m)] for __ in range(n)]

    # Quick exit if K == 0
    if K == 0:
        print("Oil : 0")
        return

    # Build 2D prefix sums
    ps = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            ps[i][j] = a[i][j]
            if i>0: ps[i][j] += ps[i-1][j]
            if j>0: ps[i][j] += ps[i][j-1]
            if i>0 and j>0: ps[i][j] -= ps[i-1][j-1]

    def rectsum(x1,y1,x2,y2):
        """Sum of a[x1..x2][y1..y2] in O(1)."""
        res = ps[x2][y2]
        if x1>0: res -= ps[x1-1][y2]
        if y1>0: res -= ps[x2][y1-1]
        if x1>0 and y1>0: res += ps[x1-1][y1-1]
        return res

    from functools import lru_cache
    INF = 10**12

    @lru_cache(None)
    def dp(row, L, R, rem, mask):
        """
        Max oil from rows row..n-1,
        if previous row used segment [L,R],
        rem cells still needed,
        mask bits: 1=left locked, 2=right locked.
        """
        # If we've processed all rows
        if row==n:
            return 0 if rem==0 else -INF
        # If no more cells to pick
        if rem==0:
            return 0
        best = -INF
        canL = not(mask & 1)
        canR = not(mask & 2)
        # Try all segments [l2..r2] in this row
        for l2 in range(m):
            for r2 in range(l2, m):
                length = r2 - l2 + 1
                if length>rem: continue
                # Must overlap with [L,R]
                if min(R,r2) < max(L,l2): continue
                # Check locks
                if (not canL) and l2 < L: continue
                if (not canR) and r2 > R: continue
                # Update mask
                nm = mask
                if l2 > L: nm |= 1
                if r2 < R: nm |= 2
                s = rectsum(row, l2, row, r2)
                val = s + dp(row+1, l2, r2, rem-length, nm)
                if val>best:
                    best = val
        return best

    # Find best starting row and segment
    ansVal = -INF
    start = None
    for row in range(n):
        for L in range(m):
            for R in range(L, m):
                length = R-L+1
                if length>K: continue
                s = rectsum(row, L, row, R)
                val = s + dp(row+1, L, R, K-length, 0)
                if val>ansVal:
                    ansVal = val
                    start = (row, L, R)

    # Output maximum
    print("Oil : {}".format(ansVal))

    # Reconstruct chosen cells
    (row, L, R) = start
    rem = K
    mask = 0
    cells = []

    # Take initial segment
    for c in range(L, R+1):
        cells.append((row+1, c+1))
    rem -= (R-L+1)
    ansVal -= rectsum(row, L, row, R)
    row += 1

    # Walk forward until rem==0
    while rem>0:
        target = ansVal
        canL = not(mask & 1)
        canR = not(mask & 2)
        found = None
        for l2 in range(m):
            for r2 in range(l2, m):
                length = r2-l2+1
                if length>rem: continue
                if min(R,r2) < max(L,l2): continue
                if (not canL) and l2<L: continue
                if (not canR) and r2>R: continue
                nm = mask
                if l2>L: nm |= 1
                if r2<R: nm |= 2
                s = rectsum(row, l2, row, r2)
                if s + dp(row+1, l2, r2, rem-length, nm) == target:
                    found = (l2, r2, nm)
                    break
            if found: break
        l2, r2, mask = found
        # Add these cells
        for c in range(l2, r2+1):
            cells.append((row+1, c+1))
        rem -= (r2-l2+1)
        ansVal -= rectsum(row, l2, row, r2)
        L, R = l2, r2
        row += 1

    # Sort and print
    cells.sort()
    for x,y in cells:
        print(x, y)

if __name__ == "__main__":
    solve()
```

5. Compressed editorial  
Use a 5-dimensional DP: state = (row, previous segment L..R, cells remaining, two-bit lock mask).  
Transitions try every new segment in current row that overlaps the old, respects locks, and subtracts its size from rem.  
Optimize sums with 2D prefix sums. Complexity O(N·M⁴·K). Reconstruct by replaying DP choices.