感觉这道题更像dp，但数据范围小，可以用dfs做

# include <iostream>
# include <cstring>
using namespace std;
int n,k,m,a[25],b[25],ma,tmp,qian,sum,zl,mark[25];void dfs(int x,int y,int zhi,int w)
{int i;if(y==k&&w<=m){if(zhi>ma)ma=zhi;return;}for(i=x+1;i<=n;i++){if(y+1<=k&&w+b[i]<=m){dfs(i,y+1,zhi+a[i],w+b[i]);mark[i]=0;}}
}int main()
{int T,i,zl;cin>>T;while(T--){ma=0;sum=0;qian=0;zl=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));cin>>n>>k;for(i=1;i<=n;i++)cin>>a[i]>>b[i];cin>>m;dfs(0,0,0,0);cout<<ma<<endl;}return 0;
}