简单背包

#include <bits/stdc++.h>
using namespace std;
const int inf = 5000005;
int n, m, t, price[105][105], f[10005];
int main(void){
//ios::sync_with_stdio(false);
cin >> t >> n >> m;
for (int i = 1; i <= t; i++){
for (int j = 1; j <= n; j++){
cin >> price[j][i];
}
}
for (int k = 1; k < t; k++){
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i++){
for (int j = price[i][k]; j <= m; j++){
f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);
}
}
m += f[m];
}
cout << m << endl;
return 0;
}