algo2017_week7_knapsack

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fo(n) for(int i=0;i<n;i++)
#define MAX 5


int main(){

    int T;

    cin >> T;

    while( T-- ){
        int n , c[MAX] , w[MAX];
        cin >> n;
        int dp[n + 1] = {0};

        fo( 5 ) cin >> w[i];
        fo( 5 ) cin >> c[i];

        fo( 5 )
            for( int j = n ; j - w[i] > -1 ; --j )
                dp[j] = max( dp[j] , dp[ j - w[i] ] + c[i] );

        cout << dp[n] << endl;
    }

    return 0;
}