//朴素写法：
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001],v[1001],w[1001];

int main()
{
    int N,V;
    cin>>N>>V;
    for(int i=1;i<=N;i++)
    cin>>v[i]>>w[i];
    for(int i=1;i<=N;i++)
    for(int j=0;j<=V;j++){
        if(j<v[i])
        dp[i][j]=dp[i-1][j];
        else
        dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);//右边的dp[i][j]包含了i-1条件下取所有件物品的最大值，而dp[i][j-v[i]]+w[i]代表了在i条件下，所有的最大值，而在取最大即为状态转移方程
    }
    cout<<dp[N][V];
    return 0;
}

//优化空间写法：

#include <bits/stdc++.h>
using namespace std;
int dp[1001],v[1001],w[1001];
int main()
{
    int N,V;
    cin>>N>>V;
    for(int i=1;i<=N;i++)
    cin>>v[i]>>w[i];
    for(int i=1;i<=N;i++)
    for(int j=v[i];j<=V;j++){
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//j是从小到大循环，所以dp[j-v[i]]<dp[j],所以dp[j-v[i]]是第二层的，所以可以直接去掉，就不用逆序输入j了
    }
    cout<<dp[V];
    return 0;
}