/*
1. 状态定义：“将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大” -> 
                当前已经选择1~i个物品， 当前体积是j -> f[i][j]  -> 属性MAX
2. 状态计算： 以当前选择的最后一个物品i划分为2个子集， 选i or 不选i，并更新体积j
                不选i：f[i][j] = f[i-1][j]
                选i： f[i][j] = f[i-1][j-v[i]] + w[i]
3。 边界： f[0][0] = 0 ， 其他=-INF 最开始时什么也没有，此时表示体积恰好为j时的最大价值
           f[~][~]  =  0 , 体积 <= j 时的最大价值
*/

import java.util.*;


public class Main{

    void run(){
        int n = jin.nextInt();
        int m = jin.nextInt();
        for (int i = 1; i <= n ; i++){
            v[i] = jin.nextInt(); 
            w[i] = jin.nextInt();
        }
        int res = dp2(n,m);
        System.out.println(res);
    }
    int dp2(int n, int m){
        int[] f = new int[maxN];
        // 可以优化成一维数组，表示体积为j时的最大价值f[j]   

        for (int i = 1 ; i <= n ; i++){
            for (int j = m; j >= v[i] ; j--){
            // j从大到小计算，所以f[j-v[i]] 其实表示的是f[i-1][j-v[i]], 因为类似滚动数组， f[j-v[i]] 还没被更新
            // 即用到上层状态从大到小枚举
            // 也正是对应了每个物品只能选一次
                f[j] = Math.max(f[j], f[j-v[i]] + w[i]);
            }
        }

        return f[m];
    }
    int dp1(int n, int m){
        int[][] f = new int[maxN][maxN];
        for (int i = 1 ; i <= n ; i++){
            for (int j = 0; j <= m; j++){
                int t = f[i-1][j];
                if (j-v[i] >= 0) t = Math.max(t, f[i-1][j-v[i]] + w[i]);
                f[i][j]  = t;
            }
        }
        int res = 0;
        for (int i = 0 ; i <= m ; i++){
            res = Math.max(f[n][i], res);
        }
        return f[n][m];
        // return res;
    }


    int maxN = 1002;

    int[] v = new int[maxN];
    int[] w = new int[maxN];
    Scanner jin = new Scanner(System.in);
    public static void main(String[] args) {new Main().run();}
}