import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[N+1];
        int[] w = new int[N+1];
        for(int i = 1; i < N+1; i++){//注意i从1开始
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        in.close();
        int res = solution(v, w, N, V);
        System.out.println(res);
    } 

    // opt[i][j]表示背包容积为 j 时，存放物品 i 时的最大价值。此时就要比较当前背包容积 j 与物品 i 的体积 va[i]，分为以下两种情况
    // (1）当 va[i] > j 时，背包肯定不能放不下物品 i，opt[i][j] = opt[i - 1][j]
    // (2) 当 va[i] <= j 时，有两种选择：放物品 i 和不放物品 i，由于是最大价值，故取两者最大值
    //    1) 放物品 i ，则opt[i][j] = wa[i] + opt[i-1][j-va[i]]
    //    2) 不放物品 i，则opt[i][j] = opt[i-1][j]
    //    3) 由于是求总价值最大，故取两者中的最大值
    // (3) opt[n][v] 即为所求
    public static int solution(int[] va, int[] wa, int n, int v){
        int[][] dp = new int[n+1][v+1];
        dp[0][0] = 0;
        for(int i = 1; i< n+1; i++){//注意i从1开始
            for(int j = 1; j < v+1; j++){//注意j从1开始
                if(j >= va[i]){
                    dp[i][j] = Math.max(dp[i-1][j-va[i]] + wa[i], dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][v];
    }
}