#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gre,profit,gr,v1[5005],v2[5005];
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) {
                v2[j]=v1[j];
            }
            else {
                v2[j]=max(v1[j] ,v1[j-gr]+profit);
            }
        }
      for (int k=1;k<=gre;k++) {
        v1[k]=v2[k];
        v2[k]=0;
      }
    }
    g << v1[gre];
    return 0;
}