/* 注意dp（动态规划问题）和贪心算法是有区别的。

dp是寻找全局最优解  - （它不会光看眼前的利益），如floyd和Bellford-man
贪心算法是寻找局部最优解，一些算法适用于它，每一步都寻找局部最优解，最后的答案就是全局最优解，如prim，Dijkstra,kruskal

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

const int N = 1010;
int v[N],w[N];  // V用来记录物品的体积，W用来记录与V中相对应物品的价值
int n,m;
int f[N][N];  //背包,一维用来遍历物品，二维用来记录背包当前的容积

int main(){

    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ ) cin >> v[i] >> w[i]; // 存出每件物品的体积以及价值;

    //创建 （物品 - 背包容积）的dp表格   
    for(int i = 1; i <= n ; i++ ){
        for(int j = 1 ; 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]); 
        }
    }


    // 方法一： 遍历一下表格最后一行
    int res = 0 ;
    for(int i = 0; i <= m; i++) res = max(res,f[n][i]);
    cout << res << endl;

    // 方法二：直接输出表格的最后一个格子，右下
    // cout << f[n][m] << endl;

    return 0;
}