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

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

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

struct Obiect {
    short 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++) {
            dp[i][j] = dp[i-1][j];
            if (j >= a[i].greutate) {
                dp[i][j] = max(dp[i][j], a[i].profit + dp[i-1][j - a[i].greutate]);
            }
        }
    }
    printf("%d\n",dp[n][g]);
    return 0;
}