#include<bits/stdc++.h>
using namespace std;
int n,m,a[1010],b[1010],dp[1010][100010];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            if(j>=a[i]) dp[i][j]=max(dp[i-1][j-a[i]]+b[i],dp[i-1][j]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    printf("%d",dp[n][m]);
    return 0;
}