2602/1リュックサック

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define MAX 10007

using namespace std;

int dp[MAX];
int w[MAX];
int c[MAX];

int main ( )
{
    unsigned t,n,m;
    scanf ( "%d" , &t );
    while ( t-- )
    {
        scanf ( "%d%d" , &n , &m );
        for ( int i = 1 ; i <= n ; i++ ) scanf ( "%d" , &w[i] );
        for ( int i = 1 ; i <= n ; i++ ) scanf ( "%d" , &c[i] );
        memset ( dp , 0 , sizeof ( dp ) );
        int ans = 0;
        for ( int i = 1 ; i <= n ; i ++ )
            for ( int j = m ; j >= c[i] ; j-- )
                ans = max ( ans , dp[j] = max ( dp[j-c[i]]+w[i] , dp[j] ));
        printf ( "%d
" , ans );
    }
}