#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// ======================= SUBTASK 1 =======================
void solve_sub1(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
bool ok = true;
for (int j = 0; j < k; j++)
{
if (r[0][j] > 0)
ok = false;
}
if (ok)
cout << 1 << "\n";
else
cout << 0 << "\n";
}
// ======================= SUBTASK 2 =======================
// Brute-force cho n, k <= 100
void solve_sub2(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
vector<ll> p(k, 0);
vector<bool> done(n, false);
int ans = 0;
while (true)
{
bool progress = false;
for (int i = 0; i < n; i++)
{
if (done[i])
continue;
bool ok = true;
for (int j = 0; j < k; j++)
{
if (p[j] < r[i][j])
{
ok = false;
break;
}
}
if (ok)
{
done[i] = true;
for (int j = 0; j < k; j++)
p[j] += u[i][j];
ans++;
progress = true;
}
}
if (!progress)
break;
}
cout << ans << "\n";
}
// ======================= SUBTASK 3 =======================
// Greedy + heap cho k = 1
void solve_sub3(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
vector<pair<ll, ll>> a(n);
for (int i = 0; i < n; i++)
{
a[i] = {r[i][0], u[i][0]};
}
sort(a.begin(), a.end()); // sort theo r[i]
ll p = 0;
int ans = 0;
int idx = 0;
priority_queue<ll> pq;
while (true)
{
while (idx < n && a[idx].first <= p)
{
pq.push(a[idx].second);
idx++;
}
if (pq.empty())
break;
ll gain = pq.top();
pq.pop();
p += gain;
ans++;
}
cout << ans << "\n";
}
// ======================= SUBTASK 4 =======================
// Phiên bản chung (mô phỏng) - có thể chạy chậm với n, k rất lớn
void solve_sub4(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
vector<ll> p(k, 0);
vector<bool> done(n, false);
int ans = 0;
while (true)
{
bool progress = false;
for (int i = 0; i < n; i++)
{
if (done[i])
continue;
bool ok = true;
for (int j = 0; j < k; j++)
{
if (p[j] < r[i][j])
{
ok = false;
break;
}
}
if (ok)
{
done[i] = true;
for (int j = 0; j < k; j++)
p[j] += u[i][j];
ans++;
progress = true;
}
}
if (!progress)
break;
}
cout << ans << "\n";
}
// ======================= MAIN =======================
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<vector<ll>> r(n, vector<ll>(k));
vector<vector<ll>> u(n, vector<ll>(k));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++)
cin >> r[i][j];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++)
cin >> u[i][j];
}
// Chia subtask
if (n == 1)
{
solve_sub1(n, k, r, u);
}
else if (n <= 100 && k <= 100)
{
solve_sub2(n, k, r, u);
}
else if (k == 1)
{
solve_sub3(n, k, r, u);
}
else
{
solve_sub4(n, k, r, u); // fallback
}
return 0;
}
