#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long unsigned
#define pb push_back
#define mp make_pair

int dp[10005];
int W[10005],P[10005];

int main(){
    int n,G,i,j;
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d %d",&n,&G);
    for(i = 1;i <= n;i++){
        scanf("%d %d",&W[i],&P[i]);
    }
    int sol = 0;
    for(i = 1;i <= n;i++){
        for(j = G-W[i];j >= 0;j--){
            dp[j+W[i]] = max(dp[j+W[i]], dp[j]+P[i]);
            sol = max(sol, dp[j+W[i]]);
        }
    }
    printf("%d",sol);
    return 0;
}