ohmy.codes

import java.io.*;

import java.util.*;

class Main{

public static void main(String[] args)throws Exception{

System.setIn(new FileInputStream("input.txt"));

BufferedReader I=new BufferedReader(new InputStreamReader(System.in));

StringBuilder as=new StringBuilder();

int ti=Integer.parseInt(I.readLine());

for(int t=1;t<=ti;t++){

StringTokenizer st=new StringTokenizer(I.readLine());

int n=Integer.parseInt(st.nextToken()),l=Integer.parseInt(st.nextToken());

int[][] food=new int[n][2];

int[] dp=new int[l+1];

TreeSet<Integer> tree=new TreeSet<>();

for(int i=0;i<n;i++){

st=new StringTokenizer(I.readLine());

food[i][1]=Integer.parseInt(st.nextToken());

food[i][0]=Integer.parseInt(st.nextToken());

}

Arrays.sort(food,Comparator.comparingInt(a->a[0]));

for(int i=0;i<n;i++){

int kal=food[i][0];

//System.out.println(dp[kal]+" "+food[i][1]);

dp[kal]=Math.max(dp[kal],food[i][1]);

ArrayList<Integer>save=new ArrayList<>();

for(int j:tree){

if(j+kal>l) break;

dp[j+kal]=Math.max(dp[j+kal],dp[j]+dp[kal]);

save.add(j+kal);

}

for(int j:save){

tree.add(j);

}

tree.add(kal);

}

int max=0;

for(int i:tree){

System.out.println("kal: "+i+" taste: "+dp[i]);

if(max<dp[i]) max=dp[i];

}

String ass=String.format("#%d %d\n",t,max);

as.append(ass);

}

System.out.println(as);

}

}