#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

struct obiect
{
    int profit, greutate;
};

// algoritmul greedy
int discretKnapsack(int K, int n, obiect obiecte[])
{
    // Making and initializing dp array
    int *dp=new int[K+1];
    fill(dp,dp+K+1,0);
    for (int i = 0; i < n; i++)
    {
        for (int w = K; w >= obiecte[i].greutate; w--)
        {
            dp[w] = max(dp[w], dp[w - obiecte[i].greutate] + obiecte[i].profit);
        }
    }
    // valoarea maxima din rucsac
    return dp[K];
}
int main()
{
    int K, N;
    obiect obiecte[10000];
    f >> N >> K;
    for (int i = 0; i < N; i++)
        f >> obiecte[i].greutate >> obiecte[i].profit;
    g << discretKnapsack(K, N, obiecte);
    return 0;
}