import java.util.*;

class Main {

    public static int knapsackWithRepeat(int[] value, int[] weight, int capacity) {
        int n = value.length; // value index start from 1, element at index 0 is 0, so as weight

        // 2D array
        // int[][] dp = new int[n][capacity + 1];
        // 朴素
        // for (int i = 1; i < n; i++)
        //     for (int c = 0; c <= capacity; c++)
        //         for (int k = 0; weight[i] * k <= c; k++)
        //             dp[i][c] = Math.max(dp[i - 1][c - weight[i] * k] + value[i] * k, dp[i][c]);
        // 优化
        // for (int i = 1; i < n; i++)
        //     for (int c = 0; c <= capacity; c++) {
        //         dp[i][c] = dp[i - 1][c];
        //         if (c >= weight[i])
        //             dp[i][c] = Math.max(dp[i][c], dp[i][c - weight[i]] + value[i]);
        //     }
        // return dp[n - 1][capacity];


        // 1D Array
        int[] dp = new int[capacity + 1];
        for (int i = 1; i < n; i++)
            for (int c = weight[i]; c <= capacity; 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 + 1];
        int[] weights = new int[n + 1];

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

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