#include <iostream>
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N][N], n, m;
int v[N], w[N];
unordered_map<int,int> mp;
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i],mp[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(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            //为什么j不能从v[i]开始：直接写f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            //如果先算了f[i-1][v1]，再算f[i][v2],而v2小于v1时，f[i][v2]=max(f[i-1][v2]...)中，f[i-1][v2]未曾计算为0。

            //如果先将v[i]排序之后呢？
            //也不行，虽然f[i][v2]=max(f[i-1][v2]，f[i-1][j-v2]+w2)中，f[i-1][v2]计算过了，但f[i-1][j-v2]有可能没有计算过，为0。
            //举个例子：v1 = 1， v2 = 2 ，v3 = 3 , j = 4;
            //  f[1][v1] = w1;
            //  f[2][v1] = 0;
        }   //  f[3][v3] = max(f[2][v3],f[2][4-v3]),其中f[2][4-v3] = f[2][1]，没有计算过。
            //而实际上，f[2][1] 应该等于 f[1][1] 不为0。
    }
    cout << f[n][m];
}