#include <algorithm>
#include<cstdio>
using namespace std;

const int NMAX = 5000;
const int GMAX = 10000;

int dp[NMAX+1][GMAX+1];

struct Obiect {
    int greutate,profit;

}a[NMAX+1];


int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int n,g,i,j;
    scanf("%d %d",&n,&g);
    for (i=1;i<=n;i++) {
        scanf("%d %d",&a[i].greutate,&a[i].profit);
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=GMAX;j++) {
            int x = dp[i-1][j];
            int y =  a[i].profit + dp[i-1][j-a[i].greutate];

            dp[i][j] = max(x,y);
        }
    }
    printf("%d\n",dp[n][g]);
    return 0;
}