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