import java.util.*;

class Main {

    public static int knapsackNoRepeat(int[] value, int[] weight, int capacity) {
        int n = value.length;
        // 2D Array
        // int[][] dp = new int[n][capacity + 1];

        // for (int c = 0; c <= capacity; c++)
        //     dp[0][c] = (weight[0] <= c) ? value[0] : 0;

        // for (int i = 1; i < n; i++)
        //     for (int c = 0; c <= capacity; c++) {
        //         dp[i][c] = dp[i - 1][c];
        //         if (weight[i] <= c)
        //             dp[i][c] = Math.max(dp[i][c], value[i] + dp[i - 1][c - weight[i]]);
        //     }
        // return dp[n - 1][capacity];

        // 1D Array
        int[] dp = new int[capacity + 1];
        for (int c = 0; c <= capacity; c++)
             dp[c] = (weight[0] <= c) ? value[0] : 0;

        for (int i = 1; i < n; i++)
            for (int c = capacity; c >= weight[i]; c--) {
                dp[c] = Math.max(dp[c], dp[c - weight[i]] + value[i]);
            }

        return dp[capacity];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        int[] values = new int[n];
        int[] weights = new int[n];

        for (int i = 0; i < n; i++) {
            weights[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }

        System.out.println(knapsackNoRepeat(values, weights, c));
    }

}