学步园

/*
分析：
    二维背包的简单题。

                               2012-07-18
*/

#include"stdio.h"
#include"string.h"


struct A
{
	int price;
	int val;
}E[111];


int max(int a,int b)
{
	return a>b?a:b;
}


int main()
{
	int T;
	int n,m,L;
	int i,l,j;
	int dp[111][1011];


	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&L);
		for(i=1;i<=n;i++)	scanf("%d%d",&E[i].price,&E[i].val);


		memset(dp,-1,sizeof(dp));
		for(j=0;j<=L;j++)	dp[0][j]=0;


		for(i=1;i<=n;i++)
		{
			for(l=m;l>=1;l--)                        //从大到小
			{
				for(j=L;j>=E[i].price;j--)           //从大到小
				{
					if(dp[l-1][j-E[i].price]==-1)	break;
					dp[l][j]=max(dp[l][j],dp[l-1][j-E[i].price]+E[i].val);
				}
			}
		}


		if(dp[m][L]==-1)	printf("0\n");
		else				printf("%d\n",dp[m][L]);
	}
	return 0;
}