46 lines
860 B
C++
46 lines
860 B
C++
#include <stdio.h>
|
|
#include <string.h>
|
|
struct node
|
|
{
|
|
int v,w;
|
|
}p[50];
|
|
int maxn,n,k,weight,vis[50];
|
|
void dfs(int wei,int val,int step,int sum)
|
|
{
|
|
if(sum == k || wei == weight)
|
|
{
|
|
if(maxn<val)
|
|
maxn = val;
|
|
return ;
|
|
}
|
|
for(int i = step;i<=n;i++)
|
|
{
|
|
if(!vis[i] && sum+1<=k && wei+p[i].w<=weight)
|
|
{
|
|
vis[i] = 1;
|
|
dfs(wei+p[i].w,val+p[i].v,i+1,sum+1);
|
|
vis[i] = 0;
|
|
}
|
|
}
|
|
return ;
|
|
}
|
|
int main()
|
|
{
|
|
int t,i,j;
|
|
scanf("%d",&t);
|
|
while(t--)
|
|
{
|
|
scanf("%d%d",&n,&k);
|
|
for(i = 1;i<=n;i++)
|
|
{
|
|
scanf("%d%d",&p[i].v,&p[i].w);
|
|
vis[i] = 0;
|
|
}
|
|
scanf("%d",&weight);
|
|
maxn = 0;
|
|
dfs(0,0,0,0);
|
|
printf("%d\n",maxn);
|
|
}
|
|
return 0;
|
|
}
|