#include <bits/stdc++.h>
using namespace std;

int wt[1005], p[1005];
int dp[10005][10005];
int main(void){
    ofstream cout("rucsac.out");
    ifstream cin("rucsac.in");
    int n, m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        cin >> wt[i] >> p[i];
    }
    for(int w = 0;w<=m;w++){
        for(int i = 0;i<=n;i++){
            if(i == 0 or w == 0){
                dp[i][w] = 0;
            }else if(wt[i] <= w){
                dp[i][w] = max(p[i] + dp[i-1][w-wt[i]], dp[i-1][w]);
            }else{
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    cout << dp[n][m];
}