/*
1. 01背包问题 :f[i][j]=max{f[i-1][j],f[i-1][j-v[i]]+w[i]}

2.完全背包问题:f[i][j]=max{f[i-1][j],f[i][j-v[i]]+w[i]}

    优化推导:
    f[i][j]=max{f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],...}
    上式的j用j-v代入，两边都加w[i]
    f[i][j-v[i]]+w[i]=max{f[i-1][j-v],f[i-1][j-2*v[i]]+w[i],...}+w[i]
    代回原式子可得
*/
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        int[] v=new int[n+1],w=new int[n+1];
        for(int i=1;i<=n;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
        }
        //int[][] f=new int[n+1][m+1];
        int[] f=new int[m+1];
        /*
        朴素做法，多加一层k循环，用于枚举0~k个物品的选择方式
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                for(int k=0;k*v[i]<=j;k++){
                    f[i][j]=Math.max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
                }
            }
        }
        */

        /*
        //对时间复杂度的优化,集合划分：f[i-1][j],f[i][j-v[i]]+w[i]
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                f[i][j]=Math.max(f[i][j],f[i-1][j]);
                if(j>=v[i]) f[i][j]=Math.max(f[i][j],f[i][j-v[i]]+w[i]);
            }
        }
        */

        //对空间复杂度也进行优化，此时f[j]为i-1层的f[i],而且f[j-v[i]]由于j-v[i]<j,是已经得到的第i层
        for(int i=1;i<=n;i++){
            for(int j=v[i];j<=m;j++){
                f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }
        System.out.println(f[m]);
    }
}