#include <bits/stdc++.h>
#define int long long int
#define endl "\n"
#define loop(i,n) for(int i=0;i<n;i++)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fileread freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define pb push_back
#define mp make_pair
#define all(v) v.begin() , v.end()
#define itr iterator
#define fi first
#define se second
#define pii pair<int,int>
#define pci pair<char,int>
#define u_map unordered_map
#define u_set unordered_set
#define u_mmap unordered_multimap
#define u_mset unordered_multiset
# define pi 3.14159265358979323846
using namespace std;

/*
    s.push_back() is used to push_back a character whereas += is used to push_back a string as well as char
    str[i] acts as both string as well as character
    if you want to iterate a string without knowing the size of the string, use '\0' in for loop
    for(int i = 0; str[i] != '\0'; i++) 
    
--------------------------------------------------------------------------------------------------------
    islower(), isupper(), tolower(), touppper();
    These methods can be used on char.
    #include<string> for there methods.

--------------------------------------------------------------------------------------------------------
    vector<int> v; 
    v.assign(n,-2);
    
    -> way to assign size of vector and fill it the entire vector with num of choice
    
    If you want to insert a value at a particular position, use insert(vector iterator, value)
    
    vector<int> vec = { 10, 20, 30, 40 }; 
    vec.insert(vec.begin() + 2, 50);
    
    vec becomes : {10, 20, 50, 30, 40}
--------------------------------------------------------------------------------------------------------

    Incase of graphs, if there are T no. of testcases, declare your adj matrix, vis and dist as local;
    This is because if you declare them global, adj.assign(n, vector<int>()) will be repeated;
    Thus size of adj and other vectors will keep on increasing;

--------------------------------------------------------------------------------------------------------

    Vector erase: v.erase(iterator); Never use for loop to use erase beacuse 1st element keeps changing;

--------------------------------------------------------------------------------------------------------

    STRING FIND: returns the index of 1st occurence of char or string passed to a string str
    the optional second argument(0 by default) specifies the initial position from where the string 
    search is to begin
    
    string str="geeks are here!";
    int found =str.find('x');
	if(found!=string::npos) cout<<found;
	else cout<<"not found";
	
	string::npos has an int value of -1;

--------------------------------------------------------------------------------------------------------
	
	STRING ERASE:
	str.erase(pos,len);  
    str.erase(itr);  
    str.erase(first,last);

--------------------------------------------------------------------------------------------------------

    To convert char to int : char c='9'; int n = c - '0';
    Similarly, to convert single digit int to char : int n = 9 ; int c = n + '0';

--------------------------------------------------------------------------------------------------------

    STRING GETLINE: before using getline for the 1st time, use : cin.ignore() once.

--------------------------------------------------------------------------------------------------------

    Convert single character to string : char c='a'; string str=to_string(c);

--------------------------------------------------------------------------------------------------------
	
    For LCM:
    int LCM(int a, int b)
    {
        return (b*a)/GCD(a,b);
    }
    
--------------------------------------------------------------------------------------------------------
    
    In math problems, if you want to find maximum value in an array of integers,
    initialize "maxx" to -INT_MAX & not to 0 (incase all intergers are negative 0 is not maximum)

--------------------------------------------------------------------------------------------------------

    character arithmetic : 
            'a'-'a' = 0
            'b'-'a' = 1
    USE : when you want to store count of characters in specific position in a vector or array,
    EX : store 'a' at 0, store 'b' at 1...
    
    given : string str= "welcome to codeforces";
            int arr[26];
            for(int i=0;i<26;i++){
                arr[str[i]-'a']++;
            }
    NO NEED TO CONVERT CHAR TO INT

--------------------------------------------------------------------------------------------------------

    In map, you can modify the value but not the key
    However, in a set of pairs, you can neither modify the first element nor the second one.
    
    In a set of pairs, the find will require the arguments as a pair of int
    
    In a map, you cannot have two entries with the same "key"
    For this purpose multimap can be used. Obviously, m[v[i]]=i does not work for multimap as v[i] is not distinct
    Use insert(make_pair(v[i],i));
    
--------------------------------------------------------------------------------------------------------

    Interactive problems : Use IOS; During cout, put "\n" at the end of cout;
                            After "\n", use cout<<flush; After that accept input;

--------------------------------------------------------------------------------------------------------

    In bit manipulation, always store the result in a temp variable and then perform comparisons
    otherwise program will give error
    
    E.g. -> this is correct :   int tmp= a & b;
                                if(tmp > 0){
                                    .....
                                }
            
            this is incorrect : if(a & b > 0){
                                    .....
                                }

--------------------------------------------------------------------------------------------------------

*/

/*
int n,m;
vector< vector <int> > adj;
vector<bool> vis;

void addedge(int u, int v){
    adj[u].pb(v);
    adj[v].pb(u);
}

void bfs(int src){
    queue<int> q;
    q.push(src);
    vis[src]=true;
    while(!q.empty()){
        int curr=q.front();
        q.pop();
        for(int i=0;i<adj[curr].size();i++){
            int node=adj[curr][i];
            if(!vis[node]){
                q.push(node);
                vis[node]=true;
            }
        }
    }
}

void printgraph(){
    for(int i=0;i<n;i++){
        cout<<i<<" -> ";
        for(int j=0;j<adj[i].size();j++) cout<<adj[i][j]<<" ";
        cout<<endl;
    }
}
*/


signed main() {
	/*
	----------
	----------
	----------
	----------
	----------
	----------
	----------
	----------
	----------
	----------
	----------
	----------
	----------
	----------
    */
    
    
    int n;//no. of items
    int w;//max. weight
    cin>>n>>w;
    //cout<<n<<" "<<w<<"\n";
    int value[n], weight[n];
    loop(i,n){
        cin>>weight[i];
        cin>>value[i];
    }
    

    vector< vector<int> > dp(n+1, vector<int>(w+1, 0));
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=w;j++) cout<<dp[i][j]<<" ";
    //     cout<<"\n";
    // }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
            if(weight[i-1] <= j){
                dp[i][j]=max(value[i-1] + dp[i-1][j-weight[i-1]], dp[i-1][j]);
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    
    
    cout<<dp[n][w];
    
    
    
}

Measured memory_bytes: 80256