import java.io.*;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new FileReader("rucsac.in"));
            String[] firstLine = br.readLine().split(" ");
            int N = Integer.parseInt(firstLine[0]);
            int G = Integer.parseInt(firstLine[1]);
            int[] weights = new int[N];
            int[] values = new int[N];

            for (int i = 0; i < N; i++) {
                String[] line = br.readLine().split(" ");
                weights[i] = Integer.parseInt(line[0]);
                values[i] = Integer.parseInt(line[1]);
            }
            br.close();

            int result = knapsack(N, G, weights, values);
            BufferedWriter bw = new BufferedWriter(new FileWriter("rucsac.out"));
            bw.write(String.valueOf(result));
            bw.close();
        } catch (Exception e) {
            System.err.println("Eroare la citirea sau scrierea fisierelor: " + e.getMessage());
        }
    }

    public static int knapsack(int N, int G, int[] weights, int[] values) {
        int[] dp = new int[G + 1];

        for (int i = 0; i < N; i++) {
            for (int w = G; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }

        return dp[G];
    }
}