#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define max(a, b) (a>b?a:b)

struct Stone
{
    int V, W;
};
Stone S[21];

int f[1005][21];

int main()
{
    int Case, N, K, L, i, j, k;
    scanf("%d", &Case);
    while(Case--)
    {
        scanf("%d%d", &N, &K);
        for(i=0; i<N; i++) scanf("%d%d", &S[i].V, &S[i].W);
        scanf("%d", &L);

        memset(f, 0, sizeof(f));
        for(i=0; i<N; i++) //物品的總個數N
            for(j=K; j>0; j--) //從N件物品中任意選K件
                for(k=L; k>=S[i].W; k--) //限定的容量L
                    f[k][j] = max(f[k][j], f[k-S[i].W][j-1]+S[i].V);
        
        int ans = 0;
        for(i=0; i<=L; i++) ans = max(ans, f[i][K]); //在限定重量L內 和 限定數量K時的最優解

        printf("%d\n", ans);
    }
}