#include<iostream>
using namespace std;
const int N = 1011;
int w[N], v[N]; // v表示物品的体积，w表示物品的价值
int f[N][N];
int n, m;
int main()
{
    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(j >= v[i]) f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);
        }
    }
    cout<<f[n][m]<<endl;

}

//简化为一维数组
#include<iostream>
using namespace std;
const int N = 1011;
int w[N], c[N]; // v表示物品的体积，w表示物品的价值
int f[N];
int n, m;

int main()
{
    int n, m; // n=5表示物品数量，m=8表示背包容纳的总重量，
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> w[i] >> c[i];

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

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