miriLawnMawer

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

const int maxn = 2000;

int a[maxn + 5][maxn + 5];
int b[maxn + 5][maxn + 5];
long long sums[maxn + 5];
long long spLin[maxn + 5][maxn + 5];
long long spCol[maxn + 5][maxn + 5];

void rotateMatrix(int n, int m) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            b[j][i] = a[i][j];
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            a[i][j] = b[i][j];
}


int solve(int n, int m, int k) {
    memset(spLin, 0, sizeof(spLin));
    memset(spCol, 0, sizeof(spCol));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            spLin[i][j] = spLin[i][j - 1] + a[i][j];
            spCol[i][j] = spCol[i - 1][j] + a[i][j];
        }
    }
    int best_ans = n * m;
    for (int max_rem_left = 0; max_rem_left < m; ++max_rem_left) {
        int up = 0, down = 0, left = 0, right = 0;
        int ans = 0;
        while (up + down < n) {
            if (spLin[up + 1][m - right] - spLin[up + 1][left] <= k) {
                up++;
                ans++;
            } else if (spLin[n - down][m - right] - spLin[n - down][left] <= k) {
                down++;
                ans++;
            } else if (spCol[n - down][left + 1] - spCol[up][left + 1] <= k && left < max_rem_left) {
                left++;
                ans++;
            } else if (spCol[n - down][m - right] - spCol[up][m - right] <= k) {
                right++;
                ans++;
            } else {
                break;
            }
        }
        if (up + down == n)
            best_ans = min(best_ans, ans);
    }
    return best_ans;
}

int main() {
//    freopen("date.in", "r", stdin);
    int k, m, n;
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);

    int ans = solve(n, m, k);
    rotateMatrix(n, m);
    ans = min(ans, solve(m, n, k));

    printf("%d\n", ans);

    return 0;
}