OIG XIV - prz

// https://szkopul.edu.pl/problemset/problem/AJdXI8LTgfnxNdN1mHhXzuir/site/?key=statement
// Przelewy

#include <bits/stdc++.h>
using namespace std;

#define int long long
constexpr int INF = INT32_MAX;

int subset_sum(const vector<int>& v, int mask) {
    int sum = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (mask & (1 << i)) {
            sum += v[i];
        }
    }
    return sum;
}

void solve() {
    int n;
    cin >> n;

    vector<int> row_sums(n);
    for (int i = 0; i < n; ++i) {
        int row_sum = 0;
        for (int j = 0; j < n; ++j) {
            int a;
            cin >> a;
            row_sum += a;
        }
        row_sums[i] = row_sum;
    }

    sort(row_sums.rbegin(), row_sums.rend());

    int limit = (1 << n);
    vector<int> dp(limit, INF);
    dp[0] = 0;

    for (int mask = 1; mask < limit; ++mask) {
        if (subset_sum(row_sums, mask) == 0) {
            dp[mask] = __builtin_popcount(mask) - 1;
        }
    }

    for (int mask = 1; mask < limit; ++mask) {
        for (int subset = mask; subset; subset = (subset - 1) & mask) {
            if (dp[subset] < INF) {
                dp[mask] = min(dp[mask], dp[subset] + dp[mask ^ subset]);
            }
        }
    }

    cout << dp[limit - 1] << '\n';
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}