Untitled

#include 
#include 

using namespace std;
const int maxn = 25;
int n, m, k;
int lock_cost[maxn];
int rating[maxn][maxn];
int cost[maxn][maxn];
int dp[maxn][1005][2];
int rec(int at_batch, int money_left, bool is_locked) {
    if(at_batch >= n) {
        return 0;
    }
    if(dp[at_batch][money_left][is_locked] != -1) {
        return dp[at_batch][money_left][is_locked];
    }
    int real_money = money_left;
    if(is_locked) {
        real_money -= lock_cost[at_batch];
    }
    int res = 0;
    if(real_money >= 0) {
        for(int i = 0; i < m; i++) {
            if(real_money >= cost[at_batch][i]) {
                res = max(res, rec(at_batch, real_money - cost[at_batch][i], false) + rating[at_batch][i]);
               
                res = max(res, rec(at_batch + 1, real_money - cost[at_batch][i], true) + rating[at_batch][i]);
            }
        }
    }
    res = max(res, rec(at_batch + 1, money_left, true));
    return dp[at_batch][money_left][is_locked] = res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    
    while(t--) {
        cin >> n >> m >> k;
        for(int i = 0; i < n; i++) {
            cin >> lock_cost[i];
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cin >> cost[i][j];
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cin >> rating[i][j];
            }
        }
        for(int i = 0; i < maxn; i++) {
            for(int j = 0; j < 1004; j++) {
                for(int k = 0; k < 2; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        cout << rec(0, k, true) << endl;
        
    }
    return 0;
}