1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 const int size = 30; 7 int weight[size] , value[size]; 8 int dp[1010][size]; 9 10 int main()11 {12     cin.sync_with_stdio(false);13     int t , n , m , w;14     cin >> t;15     while( t-- )16     {17         cin >> n >> m;18         for( int i = 0 ; i<n ; i++ )19         {20             cin >> value[i] >> weight[i];21         }22         cin >> w;23         memset( dp , 0 , sizeof(dp) );24         for( int i = 0 ; i<n ; i++ )25         {26             for( int j = w ; j>=weight[i] ; j-- )27             {28                 for( int k = m ; k>=1 ; k-- )29                 {30                     dp[j][k] = max( dp[j][k] , dp[ j-weight[i] ][ k-1 ] + value[i] );31                 }32             }33         }34         cout << dp[w][m] << endl;35     }36     return 0;37 }