stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8045079492518623x):
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=100025;

const int inf=0x3f3f3f3f;

int n,m;

int w[maxn];

ll v[maxn];

ll dp[maxn];

int main()

{

    cin>>n>>m;

    for (int i=1;i<=n;i++)

    cin>>w[i]>>v[i];

    for (int i=1;i<=n;i++)

        for(int j=m;j>=w[i];j--)

            dp[j]=max(dp[j],1ll*dp[j-w[i]]+v[i]);

    cout<<dp[m];

    return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.8046251969132598x):
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=100025;

const int inf=0x3f3f3f3f;

int n,m;

int w[maxn];

ll v[maxn];

ll dp[maxn];

int main()

{

    cin>>n>>m;

    for (int i=1;i<=n;i++)

    cin>>w[i]>>v[i];

    for (int i=1;i<=n;i++)

        for(int j=m;j>=w[i];j--)

            dp[j]=max(dp[j],1ll*dp[j-w[i]]+v[i]);

    cout<<dp[m];

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7831479714466283x):
#include <bits/stdc++.h>

using namespace std;

#define fix(f,n) std::fixed<<std::setprecision(n)<<f

#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long int ll;

typedef unsigned long long int ull;

#define vi vector<int>

#define pii pair<int,int>

#define vii vector<pii>

#define max(a,b) ((a>b)?a:b)

#define min(a,b) ((a>b)?b:a)

#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)

#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)

#define REP(i,a,n) for(ll i=a;i<n;i++)

#define pb push_back

#define mp make_pair



int main(){

	fast;

	int test=1;

	//cin >> test;

	while(test--){

	    int n,W;

	    cin >> n >> W;

	    int v[n+1],w[n+1];

	    for(int i=1 ; i<=n ; i++){

	        cin >> w[i] >> v[i];

	    }

	    ll dp[W+1][n+1]={};

	    ll maxm=-1;

	    dp[0][0]=0;

	    for(int k = 1; k <= n; k++){

	        for (int x = 0; x<=W; x++){

	            if(x>=w[k]){

	                dp[x][k]=max(v[k]+dp[x-w[k]][k-1],dp[x][k-1]);

	            }else{

	                dp[x][k]=dp[x][k-1];

	            }

	        }

	    }

	    for(int i=0 ; i<=W ; i++){

	        maxm=max(dp[i][n],maxm);

	    }

	    cout << maxm;

	}

	return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.7832638312463398x):
#include <bits/stdc++.h>

using namespace std;

#define fix(f,n) std::fixed<<std::setprecision(n)<<f

#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long int ll;

typedef unsigned long long int ull;

#define vi vector<int>

#define pii pair<int,int>

#define vii vector<pii>

#define max(a,b) ((a>b)?a:b)

#define min(a,b) ((a>b)?b:a)

#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)

#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)

#define REP(i,a,n) for(ll i=a;i<n;i++)

#define pb push_back

#define mp make_pair



int main(){

	fast;

	int test=1;

	//cin >> test;

	while(test--){

	    int n,W;

	    cin >> n >> W;

	    int v[n+1],w[n+1];

	    for(int i=1 ; i<=n ; i++){

	        cin >> w[i] >> v[i];

	    }

	    ll dp[W+1][n+1]={};

	    ll maxm=-1;

	    dp[0][0]=0;

	    for(int k = 1; k <= n; k++){

	        for (int x = 0; x<=W; x++){

	            if(x>=w[k]){

	                dp[x][k]=max(v[k]+dp[x-w[k]][k-1],dp[x][k-1]);

	            }else{

	                dp[x][k]=dp[x][k-1];

	            }

	        }

	    }

	    for(int i=0 ; i<=W ; i++){

	        maxm=max(dp[i][n],maxm);

	    }

	    cout << maxm;

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.807563815939409x):
#include<iostream>

#include<cstring> 

using namespace std;

int main()

{

	int n,w;

	cin>>n>>w;

	int wt[n+1],v[n+1];

	for(int i=1;i<=n;i++)

	cin>>wt[i]>>v[i];

	long long dp[n+1][w+1];

	memset(dp,0,sizeof(dp));

	for(int i=1;i<=n;i++)

	for(int j=1;j<=w;j++)

	{

		if(j<wt[i])

		dp[i][j]=dp[i-1][j];

		else

		dp[i][j]=max(dp[i-1][j],dp[i-1][j-wt[i]]+v[i]);

	}

	long long ans=0;

	for(int i=1;i<=n;i++)

	for(int j=1;j<=w;j++)

		if(dp[i][j]>ans)

		ans=dp[i][j];

		cout<<ans;

	

 }
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.8076812621553338x):
#include<iostream>

#include<cstring> 

using namespace std;

int main()

{

	int n,w;

	cin>>n>>w;

	int wt[n+1],v[n+1];

	for(int i=1;i<=n;i++)

	cin>>wt[i]>>v[i];

	long long dp[n+1][w+1];

	memset(dp,0,sizeof(dp));

	for(int i=1;i<=n;i++)

	for(int j=1;j<=w;j++)

	{

		if(j<wt[i])

		dp[i][j]=dp[i-1][j];

		else

		dp[i][j]=max(dp[i-1][j],dp[i-1][j-wt[i]]+v[i]);

	}

	long long ans=0;

	for(int i=1;i<=n;i++)

	for(int j=1;j<=w;j++)

		if(dp[i][j]>ans)

		ans=dp[i][j];

		cout<<ans;

	

 }
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.804824862656539x):
#include<iostream>

using namespace std;

const int maxn=105;

const int maxx=1e5+5;

int w[maxn],v[maxn];

long long dp[maxx][maxn];

int main()

{

	int n,m;

	while(cin>>n>>m)

	{

		for(int i=1;i<=n;++i)

		 cin>>w[i]>>v[i];

		for(int i=1;i<=n;++i) 

		{

			for(int j=0;j<=m;++j)

			{

				if(j-w[i]>=0)

				  dp[j][i]=max(dp[j][i-1],dp[j-w[i]][i-1]+v[i]);

				else

				  dp[j][i]=dp[j][i-1];

			}

		}

		cout<<dp[m][n]<<endl;

	}

	return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.8049421309093427x):
#include<iostream>

using namespace std;

const int maxn=105;

const int maxx=1e5+5;

int w[maxn],v[maxn];

long long dp[maxx][maxn];

int main()

{

	int n,m;

	while(cin>>n>>m)

	{

		for(int i=1;i<=n;++i)

		 cin>>w[i]>>v[i];

		for(int i=1;i<=n;++i) 

		{

			for(int j=0;j<=m;++j)

			{

				if(j-w[i]>=0)

				  dp[j][i]=max(dp[j][i-1],dp[j-w[i]][i-1]+v[i]);

				else

				  dp[j][i]=dp[j][i-1];

			}

		}

		cout<<dp[m][n]<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.801255075056498x):
#include <iostream>

using namespace std;

int n,W;

long long ans,w[110],v[110],f[110][100010];

int main()

{

	cin>>n>>W;

	for(int i=1;i<=n;i++) cin>>w[i]>>v[i];

	for(int i=1;i<=n;i++)

		for(int j=1;j<=W;j++)

		{

			f[i][j]=f[i-1][j];

			if(j>=w[i]) f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);

		}

	for(int i=1;i<=W;i++) ans=max(ans,f[n][i]);

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.801372111362832x):
#include <iostream>

using namespace std;

int n,W;

long long ans,w[110],v[110],f[110][100010];

int main()

{

	cin>>n>>W;

	for(int i=1;i<=n;i++) cin>>w[i]>>v[i];

	for(int i=1;i<=n;i++)

		for(int j=1;j<=W;j++)

		{

			f[i][j]=f[i-1][j];

			if(j>=w[i]) f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);

		}

	for(int i=1;i<=W;i++) ans=max(ans,f[n][i]);

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7641091055768336x):
#include <bits/stdc++.h>

#define SLAY ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define PI 3.141592653589793238

#define ll long long

#define pii pair<int , int>

#define pll pair<long long , long long>

#define INPUT freopen("input.txt", "r", stdin);

using namespace std;



ll solve(int i , int left , vector< vector<ll> >&dp ,vector<pll>& v ){



	if(i>=v.size())return 0;

	

	ll& ret =dp[i][left];

	

	if(~ret)return ret;

	

	if(left - v[i].first>=0){	

		ret = max(solve(i+1 , left , dp , v) , v[i].second + solve(i+1 , left - v[i].first , dp , v));

	}else{

		ret = solve(i+1 , left , dp , v) ;

	}

	

	return ret;



}



int main(){

	SLAY

	int _=1;

	// cin>>_;

	while(_--){

		ll n,m,x , y,a,b,k,ans=0, mx=LLONG_MIN, mn=LLONG_MAX;

		string str;

		cin>>n>>m;

		vector<pll> v(n);

		for(int i = 0 ; i<n ;i++){

			cin>>v[i].first>>v[i].second;

		}

		

		vector< vector<ll> > dp(n+1 , vector<ll>(m+1 , -1));

		

		for(int i = n-1 ; i>=0 ; i-- ){

			for(int j = 0 ; j <= m ; j++){

				solve(i , j , dp , v);

			}

		}

		cout<<solve(0, m , dp , v);

		cout<<endl;

	}

	return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.764223728328795x):
#include <bits/stdc++.h>

#define SLAY ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define PI 3.141592653589793238

#define ll long long

#define pii pair<int , int>

#define pll pair<long long , long long>

#define INPUT freopen("input.txt", "r", stdin);

using namespace std;



ll solve(int i , int left , vector< vector<ll> >&dp ,vector<pll>& v ){



	if(i>=v.size())return 0;

	

	ll& ret =dp[i][left];

	

	if(~ret)return ret;

	

	if(left - v[i].first>=0){	

		ret = max(solve(i+1 , left , dp , v) , v[i].second + solve(i+1 , left - v[i].first , dp , v));

	}else{

		ret = solve(i+1 , left , dp , v) ;

	}

	

	return ret;



}



int main(){

	SLAY

	int _=1;

	// cin>>_;

	while(_--){

		ll n,m,x , y,a,b,k,ans=0, mx=LLONG_MIN, mn=LLONG_MAX;

		string str;

		cin>>n>>m;

		vector<pll> v(n);

		for(int i = 0 ; i<n ;i++){

			cin>>v[i].first>>v[i].second;

		}

		

		vector< vector<ll> > dp(n+1 , vector<ll>(m+1 , -1));

		

		for(int i = n-1 ; i>=0 ; i-- ){

			for(int j = 0 ; j <= m ; j++){

				solve(i , j , dp , v);

			}

		}

		cout<<solve(0, m , dp , v);

		cout<<endl;

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.827088462332068x):
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;



typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,

tree_order_statistics_node_update> indexed_set;

typedef long long ll;

const int N = 1e5+10 , OO = 0x3f3f3f3f , mod = 1e9 + 7;



#define PI acos(-1) 

#define clr(arr,val) memset(arr , val , sizeof (arr))

#define loop(i,n) for(int i = 0;i < int(n);i++)

#define rloop(i,n) for(int i = int(n)-1;i >= 0;i--)

#define xloop(i,a,b) for(int i = int(a);i <= int(b);i++)

#define range(vec) for(auto &x : vec) cin >> x;

#define ALL(v) ((v).begin()) , ((v).end())

#define SZ(v)  ((int)((v).size()))

int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction

//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction

//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction

//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction

 

char grid[1005][1005];

int n , k , w[105] , v[105];

ll dp[105][N];





int main()

{

  //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  

  scanf("%d %d", &n,  &k);

  for(int i = 0 ; i < n ; ++i)

    scanf("%d %d", &w[i], &v[i]);

  

  for(int idx = n-1 ; idx >= 0 ; --idx){

    for(int remW = 0 ; remW <= k ; ++remW){

      ll leave = dp[idx + 1][remW];

			ll take = (remW - w[idx]) < 0 ? (-OO*1LL*OO) : (v[idx] + dp[idx + 1][remW - w[idx]]);

      dp[idx][remW] = max(leave , take);

    }

  } 

  printf("%lld\n", dp[0][k]);



  return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.8272071771592673x):
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;



typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,

tree_order_statistics_node_update> indexed_set;

typedef long long ll;

const int N = 1e5+10 , OO = 0x3f3f3f3f , mod = 1e9 + 7;



#define PI acos(-1) 

#define clr(arr,val) memset(arr , val , sizeof (arr))

#define loop(i,n) for(int i = 0;i < int(n);i++)

#define rloop(i,n) for(int i = int(n)-1;i >= 0;i--)

#define xloop(i,a,b) for(int i = int(a);i <= int(b);i++)

#define range(vec) for(auto &x : vec) cin >> x;

#define ALL(v) ((v).begin()) , ((v).end())

#define SZ(v)  ((int)((v).size()))

int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction

//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction

//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction

//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction

 

char grid[1005][1005];

int n , k , w[105] , v[105];

ll dp[105][N];





int main()

{

  //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  

  scanf("%d %d", &n,  &k);

  for(int i = 0 ; i < n ; ++i)

    scanf("%d %d", &w[i], &v[i]);

  

  for(int idx = n-1 ; idx >= 0 ; --idx){

    for(int remW = 0 ; remW <= k ; ++remW){

      ll leave = dp[idx + 1][remW];

			ll take = (remW - w[idx]) < 0 ? (-OO*1LL*OO) : (v[idx] + dp[idx + 1][remW - w[idx]]);

      dp[idx][remW] = max(leave , take);

    }

  } 

  printf("%lld\n", dp[0][k]);



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8288946682827845x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + 9;

inline int read()

{

    int data = 0, f = 1;

    char ch = getchar();

    while (!isdigit(ch))

    {

        if (ch == '-')

            f = -1;

        ch = getchar();

    }

    while (isdigit(ch))

    {

        data = (data << 3) + (data << 1) + ch - '0';

        ch = getchar();

    }

    return f * data;

}

int p[109], v[109];

ull dp[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("data.txt","w",stdout);

    //std::ios::sync_with_stdio(false);

    //std::cin.tie(0);

    int n = read(), w = read();

    for (int i = 1; i <= n; ++i)

        p[i] = read(), v[i] = read();

    for (int i = 1; i<= n; ++i)

        for (int j = w; j >= p[i]; --j)

            dp[j] = max(dp[j], dp[j - p[i]] + v[i]);

    cout << dp[w] <<'\n';

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.8290135004679724x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + 9;

inline int read()

{

    int data = 0, f = 1;

    char ch = getchar();

    while (!isdigit(ch))

    {

        if (ch == '-')

            f = -1;

        ch = getchar();

    }

    while (isdigit(ch))

    {

        data = (data << 3) + (data << 1) + ch - '0';

        ch = getchar();

    }

    return f * data;

}

int p[109], v[109];

ull dp[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("data.txt","w",stdout);

    //std::ios::sync_with_stdio(false);

    //std::cin.tie(0);

    int n = read(), w = read();

    for (int i = 1; i <= n; ++i)

        p[i] = read(), v[i] = read();

    for (int i = 1; i<= n; ++i)

        for (int j = w; j >= p[i]; --j)

            dp[j] = max(dp[j], dp[j - p[i]] + v[i]);

    cout << dp[w] <<'\n';

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

   for(int i=1;i<=n;++i){

       cin>>w[i]>>v[i];

   }

   for(int i=1;i<=n;++i){

       for(int j=m;j>=0;--j){

           if(j-w[i]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8066079988328665x):
#include <iostream>

#include <cassert>

#include <algorithm>

#define N int(1e5+1)



using namespace std;

typedef pair<int,int>pii;

long long dp[N];

pii a[100];

int main(int argc,char ** argv)

{

    int n,w;

    cin>>n>>w;

    for(int i=0;i<n;++i)cin>>a[i].first>>a[i].second;   

    for(int i=0;i<n;++i){

        for(int j=w;j>=a[i].first;--j){

            dp[j]=max(dp[j],dp[j-a[i].first]+a[i].second);

        }

    }

    cout<<dp[w]<<endl;

    return 0;

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

	for(int i = 1;i<=n;++i){

		cin>>w[i]>>v[i];

	}

	

	memset(f,0,sizeof(f));

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

			f[j] = max(f[j],f[j-w[i]]+v[i]);

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Faster C++ solution for the same problem (measured speedup: 1.8067253829447034x):
#include <iostream>

#include <cassert>

#include <algorithm>

#define N int(1e5+1)



using namespace std;

typedef pair<int,int>pii;

long long dp[N];

pii a[100];

int main(int argc,char ** argv)

{

    int n,w;

    cin>>n>>w;

    for(int i=0;i<n;++i)cin>>a[i].first>>a[i].second;   

    for(int i=0;i<n;++i){

        for(int j=w;j>=a[i].first;--j){

            dp[j]=max(dp[j],dp[j-a[i].first]+a[i].second);

        }

    }

    cout<<dp[w]<<endl;

    return 0;

}