1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #define MAX(A,B) (A>B?A:B)
 5 int n, k, W;//n块石头 制作一条项链所需要的宝石数量k 最大承受重量 W
 6 int v[35], w[35], ans;//每块石头的价值v[i] 重量w[i]
 7 
 8 void DFS(int Nstone, int whight,int value,int a)//现在已经拥有的宝石数量 现在项链的重量 现在项链的价值 判断第a块石头要或者不要
 9 {
10     if(Nstone == k && whight <= W)//满足条件 取最大值
11     {
12         ans = MAX(value, ans);
13         return ;
14     }
15     if(whight > W || a >= n || Nstone > n)//越界 退出
16         return ;
17     DFS(Nstone+1,whight+w[a],value+v[a],a+1);//要这块石头
18     
19     DFS(Nstone,whight,value,a+1);//不要这块石头
20 }
21 int main()
22 {
23     int Ncase, i;
24     scanf("%d",&Ncase);
25     while(Ncase--)
26     {
27         scanf("%d%d",&n,&k);
28         for( i = 0; i < n; i++)
29             scanf("%d%d",&v[i],&w[i]);;
30         scanf("%d",&W);
31         ans = 0;
32         DFS(0,0,0,0);
33         printf("%d\n",ans);
34     }
35     return 0;
36 }