package swea;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
* N개, L칼로리를 넘겨선 안되는 조건
* dp로 풀 수 있는가?
* 부분집합이 존재하는가?
*
*
*
* */

public class Q5212_v2 {

    static int T, N, L;
    static int[][] dp;
    static int[] scores;
    static int[] cals;

    static BufferedReader br;
    static StringTokenizer st;

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        dp = new int [N+1][L+1];
        scores = new int[N+1];
        cals = new int[N+1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int score = Integer.parseInt(st.nextToken());
            int cal = Integer.parseInt(st.nextToken());

            scores[i] = score;
            cals[i] = cal;

        }
    }

    public static void solve() {
        for (int i = 1; i <= N; i++) {
            for (int c = 1; c <= L; c++) { // 최대 칼로리
                // 넣는경우
                // 안넣는 경우
                if (cals[i] <= c) { // 최대 칼로리 제한 성리
                    // clas[i-1]을 빼고 cals[i]를 넣는 것이 더 좋다면 처리
                    if (scores[i] + dp[i-1][c - cals[i]] > dp[i-1][c]) {
                        dp[i][c] = scores[i] + dp[i-1][c-cals[i]];
                    } else { // 이전 점수가 더 크면 그대로 사용
                        dp[i][c] = dp[i-1][c];
                    }
                } else {
                    dp[i][c] = dp[i-1][c];
                }
            }
        }
    }

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

        System.setIn(new FileInputStream("./swea/txt/Q5212.txt"));
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            input();
            solve();
            System.out.println("#" + tc + " " + dp[N][L]);
        }

    }
}