//题意：一共有n个物品，每个物品有他的价值和体积。
//你有一个背包，容量为m，求背包装物品的最大价值是多少。

//每个物品都有俩种选择：选或不选

//状态表示：f[i][j]只选前i个物品，容积最大为j，的最大价值
//f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
int v[N],w[N],f[N][N];
int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(v[i]<=j)f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);

        }

    cout<<f[n][m];    
}


//以上是二维操作，但我们仅根据体积来判断
//不过我们再操作体积是要倒序操作，因为在二维中我们是用f[i-1][j]来///更新f[i][j->next],如果正序操作,f[i][j]会在f[i][j->next]前进行，///那么我们就是用了f[i][j]来更新f[i][j->next]

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2020;
int v[N],w[N],f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        for(int j=m;j>=v[i];j--)
        f[j]=max(f[j-v[i]]+w[i],f[j-1]);
    }

    cout<<f[j];
}