#include<iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int val;
int vol;
}Node;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dp[1005][1005];
Node a[1005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int text;
cin>>text;
while(text--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int n,c;
cin>>n>>c;
int i,j;
for(i = 1;i <= n;i++)
cin>>a[i].val;
for(i = 1;i <= n;i++)
cin>>a[i].vol;
for(i = 0;i < a[1].vol;i++)
dp[1][i] = 0;
for(i = a[1].vol;i <= c;i++)
dp[1][i] =a[1].val;
for(i = 2;i <= n;i++)
for(j = 0;j <= c;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(a[i].vol > j)
dp[i][j] = dp[i-1][j];
else if(dp[i-1][j] > dp[i-1][j-a[i].vol] + a[i].val)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i-1][j-a[i].vol] + a[i].val;
}
cout<<dp[n][c]<<endl;
}
return 0;
}