<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

167. I-country.
time limit per test: 0.75 sec.
memory limit per test: 65536 KB
input: standard
output: standard



According to top-secret A-country plans, I-country is divided into N*M equal squares, each square contains some oil resources. They want to occupy all the territory of I-country, but the UN (United Nations) will allow them to occupy only K squares. Of course, A-country want to get control over as many oil as possible, but, they will have to guard all their territory. So, they need their territory to be easy-controlled, i.e. from any square to any it must be possible to get moving only along two directions (selected from the next list: left, right, up, down; for different squares pairs of directions may differ).
You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.

Input
On the first line of input there are 3 integer numbers N,M,K (1<=N,M<=15, 0<=K<=N*M). Next N lines contains M integers each, which are the number of oil resource on that square. Each of this numbers lies in range of 0 to 1000.

Output
On the first line of output, write string "Oil : X", where integer number X --- the maximal number of oil which can be controlled by A-country. Next you should output K pairs of numbers --- coordinates of the squares which will be occupied by A-country. The first coordinate is number of row (top to bottom, starting from 1), second is number of column (left to right, starting from 1).

Sample test(s)

Input
2 3 4
10 20 30
40 2 3

Output
Oil : 100
1 1
1 2
1 3
2 1
Author:	NNSU #2 team
Resource:	
Date:

<|response|>
1. Abridged problem statement  
Given an N×M grid of nonnegative oil values and an integer K, choose exactly K cells so that  
  • In every row where you pick cells, the chosen cells form one contiguous segment [lᵢ, rᵢ].  
  • Segments in consecutive chosen rows overlap by at least one column (so the occupied shape is row‐connected).  
  • The left endpoints lᵢ never “re‐expand” once they move right, and the right endpoints rᵢ never “re‐expand” once they move left (this unimodal constraint guarantees you can travel between any two picked cells with at most two of the four directions).  
Maximize the total oil in the K chosen cells, and output one example of a valid selection achieving that maximum.

2. Key observations  
• Any valid occupied shape can be described by, for each row, an interval [l, r]. Connectivity requires each [lᵢ, rᵢ] to overlap [lᵢ₋₁, rᵢ₋₁].  
• The “once you shrink you can’t grow back” on the left and right boundaries can be enforced by two boolean “lock” flags: once lᵢ > lᵢ₋₁, the left side is locked (you cannot later pick an interval that starts to the left); similarly for the right side.  
• We need exactly K cells in total.  
• We can do a DP over rows, remembering:  
    – current row index,  
    – previous row’s segment [pl, pr],  
    – number of cells still to pick rem,  
    – 2‐bit mask of which sides are locked.  
• Transitions try every potential new segment [l, r] on this row that:  
    1. has length ≤ rem,  
    2. overlaps [pl, pr],  
    3. respects locks (if left is locked, l ≥ pl; if right locked, r ≤ pr),  
    4. updates the locks if you shrink from one side.  
• Precompute prefix sums per row to get segment sums in O(1).  
• DP state count is O(N·M²·K·4), transitions each loop O(M²) → overall ~O(N·M⁴·K), which is fine for N,M ≤ 15 and K ≤ 225.  
• Finally, we try every possible starting row and starting segment [l,r], use the DP to get the best total, then reconstruct one valid sequence of segments.

3. Full solution approach  
a) Read N,M,K and the grid a[i][j].  
b) Build, for each row i, a 1D prefix sum rowSum[i][c] = sum of a[i][0..c].  
c) Define a DP function rec(row, pl, pr, rem, mask) that returns the maximum oil sum from rows row…N−1 if:  
   – in row−1 we used segment [pl, pr],  
   – we still need to pick rem cells,  
   – mask bit0=1 means left is locked, bit1=1 means right is locked.  
   Base cases:  
     • If row == N, return 0 if rem == 0 else −∞.  
     • If rem == 0 but row < N, return 0 (we can pick no more).  
   Recurrence: try all l, r with 0 ≤ l ≤ r < M:  
     1. len = r−l+1 ≤ rem  
     2. overlapLen = min(pr, r) − max(pl, l) + 1 > 0  
     3. if (mask&1) and l < pl, skip; if (mask&2) and r > pr, skip.  
     4. newMask = mask; if l>pl set bit0; if r<pr set bit1.  
     5. s = rowSum[row][r] − (l>0 ? rowSum[row][l−1] : 0).  
     6. candidate = s + rec(row+1, l, r, rem−len, newMask).  
     Take the maximum over all valid (l,r).  
d) Initialize a global best answer = −∞. Loop over every possible startRow in [0..N−1] and every segment [l,r] in that row with length ≤ K, compute s₀ for that segment, then val = s₀ + rec(startRow+1, l, r, K−len, 0). Track the best val and store the corresponding startRow, l, r.  
e) Reconstruction:  
   – Let rem = K, row = startRow, pl = startL, pr = startR, mask=0.  
   – Output all cells (row, c) for c=pl..pr. rem−=len. row++.  
   – While rem>0: compute curDP = rec(row, pl, pr, rem, mask). Loop over all valid next segments [l,r] as before; find the one where s + rec(row+1,l,r,rem−len,newMask) == curDP.  
     • Append those cells, update rem, mask, pl=l, pr=r, row++.  
f) Sort the list of chosen cells by (row, col), add +1 to make 1‐based indices, and print.

4. C++ implementation
```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;
}
```

5. Python implementation with detailed comments  
```python
import sys
sys.setrecursionlimit(10**7)
from functools import lru_cache

def solve():
    data = sys.stdin.read().split()
    it = iter(data)
    N, M, K = map(int, (next(it), next(it), next(it)))
    # Read grid
    a = [list(map(int, (next(it) for _ in range(M)))) for __ in range(N)]

    # If K==0, answer is trivial
    if K == 0:
        print("Oil : 0")
        return

    # Build row‐prefix sums
    rowSum = [[0]*M for _ in range(N)]
    for i in range(N):
        acc = 0
        for j in range(M):
            acc += a[i][j]
            rowSum[i][j] = acc

    INF = 10**15

    @lru_cache(None)
    def rec(row, pl, pr, rem, mask):
        """
        Return max oil from rows[row..N-1], given previous segment [pl, pr],
        rem cells still needed, mask bit0=left locked, bit1=right locked.
        """
        if row == N:
            return 0 if rem == 0 else -INF
        if rem == 0:
            return 0

        best = -INF
        leftLocked  = (mask & 1)
        rightLocked = (mask & 2)

        for l in range(M):
            for r in range(l, M):
                length = r - l + 1
                if length > rem: continue
                # Must overlap previous
                if min(pr, r) < max(pl, l): continue
                # Respect locks
                if leftLocked  and l < pl: continue
                if rightLocked and r > pr: continue
                nm = mask
                if l > pl: nm |= 1
                if r < pr: nm |= 2
                s = rowSum[row][r] - (rowSum[row][l-1] if l>0 else 0)
                val = s + rec(row+1, l, r, rem - length, nm)
                if val > best:
                    best = val
        return best

    # Find best starting row and segment
    bestTotal = -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
                s0 = rowSum[row][r] - (rowSum[row][l-1] if l>0 else 0)
                val = s0 + rec(row+1, l, r, K - length, 0)
                if val > bestTotal:
                    bestTotal = val
                    start = (row, l, r)

    print("Oil : {}".format(bestTotal))

    # Reconstruct one solution
    row, pl, pr = start
    rem = K
    mask = 0
    ans = []

    # Take initial segment
    for c in range(pl, pr+1):
        ans.append((row, c))
    rem -= (pr - pl + 1)
    row += 1

    # Step through remaining rows
    while rem > 0:
        curDP = rec(row, pl, pr, rem, mask)
        leftLocked  = (mask & 1)
        rightLocked = (mask & 2)
        found = False
        for l in range(M):
            if found: break
            for r in range(l, M):
                length = r - l + 1
                if length > rem: continue
                if min(pr, r) < max(pl, l): continue
                if leftLocked  and l < pl: continue
                if rightLocked and r > pr: continue
                nm = mask
                if l > pl: nm |= 1
                if r < pr: nm |= 2
                s = rowSum[row][r] - (rowSum[row][l-1] if l>0 else 0)
                if s + rec(row+1, l, r, rem - length, nm) == curDP:
                    # Choose this segment
                    for c in range(l, r+1):
                        ans.append((row, c))
                    rem -= length
                    pl, pr, mask = l, r, nm
                    found = True
                    break
        row += 1

    # Sort & print in 1‐based coords
    ans.sort()
    for i, j in ans:
        print(i+1, j+1)

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

Explanation of the Python code:  
- We build per‐row prefix sums for O(1) segment queries.  
- We use `@lru_cache` to memoize the recursive DP `rec(row, pl, pr, rem, mask)`.  
- We then try all possible starting positions to get the global best.  
- Reconstruction uses the same DP to find a valid next segment that realizes the optimum.  
- Finally, we output “Oil : X” and the list of K coordinates in any order (we sort them for neatness).