#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=5e3+5,K=1e4+5;
int dp[K];
signed main()
{
    ifstream cin("rucsac.in");ofstream cout("rucsac.out");
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        int a,b;cin>>a>>b;
        for(int j=k;j>=a;--j) dp[j]=max(dp[j],dp[j-a]+b);
    }
    int ans=0;
    for(int i=0;i<=k;++i) ans=max(ans,dp[i]);
    cout<<ans;
}