#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int mat[5005][10005],n,gre,profit[5005],gr[5005];
int main()
{
    f >> n >> gre;
    for (int i=1;i<=n;i++) {
        f >> gr[i] >> profit[i];
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=gre;j++) {
            if (gr[i]>j) {
                mat[i][j]=mat[i-1][j];
            }
            else {
                mat[i][j]=max(mat[i-1][j], mat[i-1][j-gr[i]]+profit[i]);
            }
        }
    }
    g << mat[n][gre];
    return 0;
}