#include <iostream>

    /*由于f[i][j]表示在面对i件物品的时候 背包体积为j的时候的最大价值转移的状态来自仅来自两个
    /*如果当前物品体积大于背包体积表示不能在装同种物品了 转移的状态来自与前i-1件物品的最大价值
    /*如果当前物品体积小于等于背包体积 转移的状态则有一下两个状态 取其最大值即可 
    /*1. 前i-1件物品的最大价值       f[i-1][j]
    /*2. 装下同种物品后i件物品背包容量为j-w的最大值 由于物品可以无限用所以是面对i件物品  f[i][j-w] +v /*(如果是01背包的话就 同种物品只能选一次 状态转移方程为 f[i - 1][j-w] +v)*/
using namespace std;
const int nm = 1e3 + 10;
struct Good{
    int w;//重量
    int v;//价值
}goods[nm];
int f[nm][nm];
int main()
{

    int n,w;
    cin >> n>> w;
    for(int i = 1;i<=n;i++) scanf("%d%d",&goods[i].w,&goods[i].v);
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=w;j++)
        {
           f[i][j] =f[i -1][j];
           if(goods[i].w <= j)
           {
               f[i][j] = max(f[i][j],f[i][j-goods[i].w] +goods[i].v);//状态转移
           }
        }
    }
    cout << f[n][w];
    return 0;
}