题目本身暗示了大概什么算法。那么多天，那么多商品，DFS什么的肯定不行。题目说金子的最大值不能超过1万是蛮重要的。不用考虑长期持有一个商品，每天把商品都卖了，然后再买从这天到接下来一天增值最多的组合。这样每天的问题都变成一个完全背包问题。今天的金币数量就是背包的容量，每个商品今天的价格就是物品体积，而第二天的价格就是物品的价值。这里有个地方和背包问题不一样的就是如果什么都不装（不花钱）每个金币到第二天也是有价值的。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;//, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) { ch = getchar();}
    while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x;// * f;
}
int main() {
    int t = read(), n = read(), g = read();
    if (t <= 1) { cout << g; return 0;}
    int p[n][t], v[10005];
    for (register int d = 0; d < t; d++)
        for (register int i = 0; i < n; i++) p[i][d] = read();
    for (register int d = 0; d < t - 1; d++) {
        v[0] = 0;
        for (register int m = 1; m <= g; m++) {
            v[m] = v[m - 1] + 1;
            for (register int i = 0; i < n; i++) {
                if (p[i][d] >= p[i][d + 1] or m < p[i][d]) continue;
                v[m] = max(v[m], v[m - p[i][d]] + p[i][d + 1]);
            }
        }
        g = v[g];
    }
    cout << g;
    return 0;
}