#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("rucsac.in");
ofstream g ("rucsac.out");
int n,w;
int dp[10001];
int gr,cost;
int main()
{
    f >> n>> w;
    for(int i= 1;i<=n;i++)
    {
        f >> gr >> cost;
        /// din cauza faptului ca in matricea de programare dinamica folosim doar randul anterior
        /// putem folosi doar un vector pe care il luam de la dr la st si modificam valorile
        for(int j = w;j>=gr;j--)
            dp[j] =  max(dp[j],dp[j-gr]+cost);

    }
    g << dp[w];
}