#include <bits/stdc++.h> using namespace std; #define ll long long #define FOR(i, l, r) for(int i = l; i <= r; i++) #define FORD(i, l, r) for(int i = l; i >= r; i--) #define db double #define ldb long double #define all(x) (x).begin(), (x).end() #define ins insert #define pb push_back int n, k; vector<vector<int>> r, u; namespace sub1{ void sol(){ FOR(i, 1, k) if(r[1][i] > 0) return void(cout << "0\n"); cout << "1\n"; } } namespace sub2{ void sol(){ vector<ll>p(k + 1); vector<bool> used(n + 1, false); int ans = 0; bool can = true; while(can){ can = false; FOR(i, 1, n){ if(used[i]) continue; bool ok = true; FOR(j, 1, k) if(p[j] < r[i][j]){ ok = false; break; } if(ok){ ++ans; used[i] = true; can = true; FOR(j, 1, k) p[j] += u[i][j]; } } } cout << ans << "\n"; } } namespace sub3{ void sol(){ vector<pair<int,int>> a; FOR(i, 1, n) a.pb({r[i][1], i}); sort(all(a)); priority_queue<ll> pq; ll p = 0; int j = 0, ans = 0; while(true){ while(j < n && a[j].first <= p){ pq.push(u[a[j].second][1]); ++j; } if(pq.empty()) break; p += pq.top(); pq.pop(); ++ans; } cout << ans << "\n"; } } void solve(){ cin >> n >> k; r.assign(n + 1, vector<int>(k + 1, 0)); u.assign(n + 1, vector<int>(k + 1, 0)); FOR(i, 1, n)FOR(j, 1, k) cin >> r[i][j]; FOR(i, 1, n)FOR(j, 1, k) cin >> u[i][j]; if(n == 1) sub1::sol(); else if(n <= 100 && k <= 100) sub2::sol(); else if(k == 1) sub3::sol(); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; } /* n modules k topics dau tien kien thuc benson cua topic j la p[j] = 0 chi co the hoan thanh modulo i neu p[j] >= r[i][j] voi moi j sau khi hoan thanh modulo i thi p[j] += u[i][j] voi moi j tham lam p[j] >= r[i][j] moi co the an dc phai hoan thanh 1 modulo thi moi co the tang dc knowledge */