honsLawnMowingVlad

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>


#define NMAX (int)(2e3 + 2)
#define MMAX (int)(2e3 + 2)
#define INF (int)(1e9)
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {cerr << '{'; __print(std::get<0>(x)); cerr << ','; __print(std::get<1>(x)); cerr << ','; __print(std::get<2>(x)); cerr << '}';}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

enum REMOVE {top_row, bottom_row, left_col, right_col};

struct Candidate {
    ll val;
    REMOVE type;
};


int  N, M, K;
vector<vector<int>> a, aT;


/*
 * Returns the sum of the submatrix that spans: top_left corner: {i_up, j_up} and bottom_right corner {i_down, j_down}
 *
 */
int get_sum(const vector<vector<int>>& prefix_sum, int i_up, int j_up, int i_down, int j_down) {
    // See notes for drawing
    return prefix_sum[i_down][j_down] -  prefix_sum[i_up - 1][j_down] - prefix_sum[i_down][j_up - 1] + prefix_sum[i_up - 1][j_up - 1];
}

/*
 * Helper funtctions that computes the prefix sum of `a` : N x M (2D array) and returns it
 * Returns: N x M matrix of prefix sum
 */
vector<vector<int>> precompute_prefix_sum(const vector<vector<int>>& a, int N, int M) {
    //Reference:  https://www.pbinfo.ro/articole/5615/sume-partiale-in-tablouri
     vector<vector<int>> prefix_sum(N + 1, vector<int>(M + 1, 0));
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            prefix_sum[i][j] = a[i][j] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1];
    return prefix_sum;
}

/*
 * Helper function that reduces all Rows of 2D Array `a`, where `a`: N x M
 * Returns: min. # of mowing sessions required
 */
int solve (const vector<vector<int>>& a, int N, int M) {

    vector<vector<int>> prefix_sum = precompute_prefix_sum(a, N, M);

    int mn = N + M - 1; // worst-case solution

    for (int remove_left_cols = 0; remove_left_cols <= M - 1; ++remove_left_cols) { // O(M)
        // Try removing all rows; when stuck (no row is removable): remove `remove_left_cols` columns from the left; when we get stuck: remove columns from the right as many as needed
        // if no solution found => We cannot solve the problem w/ these many "tokens"

        // NOTE: the order of removing top or bottom row is IRRELEVANT, as in the end we will have been removed all the rows

        int top = 1, bottom = N, left = 1, right = M;
        bool foreverStuck = false;

        while (top <= bottom && !foreverStuck) { //  while there are still rows to be removed; O(N + M)
           if (get_sum(prefix_sum, top, left, top, right) <= K)  // top row can be removed
               top ++;
            else if (get_sum(prefix_sum, bottom, left, bottom, right) <= K) // bottom row can be removed
                bottom --;
            else if (remove_left_cols > left - 1 && get_sum(prefix_sum, top, left, bottom, left) <= K) // Stuck from removing rows => if we allow ourselves to still remove rows from the left & `k` constraint holds
                left ++; // left col can be removed
            else if (get_sum(prefix_sum, top, right, bottom, right) <= K) // `k` constraint can be removed and no other row/col can be removed (for rows we are stuck, for cols we can't remove `left` col anymore
                right --;
            else
                foreverStuck = true;
        }

        if (!foreverStuck) // potential solution found
        {
            int left_cols_removed = left - 1;
            int right_cols_removed = M - right;
            int cand = N + left_cols_removed + right_cols_removed; // `N` = all rows were removed
            mn = min(mn, cand);
        }

    }

    return mn;
}

int main() { // O((N + M) ^ 2) TC
    // TC Analysis:
    // Case 1: remove all rows : O(M * (N +M)) = O(M*N + M^2)
    // Case 2: remoev all cols <=> remove all rows in aT (transpose of `a` 2D array): O(N * (N + M)) = O(N^2 + NM)
    // Summing up these 2 cases: O((N+M)^2) tc

//    freopen("instances/small/22_test.in", "r", stdin);
//    freopen("instances/small/22_test.out", "w", stdout);

    // N * M matrix
    cin >> K >> M >> N;

    a.resize(N + 1, vector<int>(M + 1));
    aT.resize(M + 1, vector<int>(N + 1));

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) {
            cin >> a[i][j];
            aT[j][i] = a[i][j];
        }


    int minReduceAllRows = solve(a, N, M);
    int minReduceAllCols = solve(aT, M, N);
    int ans = min(minReduceAllRows, minReduceAllCols);

    std::cout << ans << '\n';


    return 0;
}