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.8059129892545456x):
#include <bits/stdc++.h>

using namespace std;

int  main(){

        long long  n, w; cin>>n>>w;

        long long wt[10000],val[10000];

        for(int i=0;i<n;i++)cin>>wt[i]>>val[i];

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

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

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

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

        		if(j>=wt[i-1])dp[i][j]=max(dp[i-1][j], val[i-1]+dp[i-1][j-wt[i-1]]);

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

        	}

        }

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

}
// 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.8060303282082286x):
#include <bits/stdc++.h>

using namespace std;

int  main(){

        long long  n, w; cin>>n>>w;

        long long wt[10000],val[10000];

        for(int i=0;i<n;i++)cin>>wt[i]>>val[i];

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

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

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

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

        		if(j>=wt[i-1])dp[i][j]=max(dp[i-1][j], val[i-1]+dp[i-1][j-wt[i-1]]);

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

        	}

        }

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

}
// 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.7828425580551244x):
#include <bits/stdc++.h>



#define cn count

#define pb push_back

#define in insert

#define fs first

#define sc second

#define sz size

#define len length

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)

#define forni(i, n) for (ll i = 1; i < (ll) (n); ++i)

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



using namespace std;

using ll = long long;

const ll inf = 1e9+7; 

const double PI =  3.141592653589793;



int main(){

	IO;

	ll n,w,wi,vi;

	cin>>n>>w;

	ll dp[w+1];

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

	forn(i,n){

		cin>>wi>>vi;

		for(ll j = w-wi; j>=0; j--) dp[j+wi] = max(dp[j+wi],dp[j]+vi);

	}

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

	return 0;

}





// _   .-')                .-. .-')                 .-')                                               

//( '.( OO )_              \  ( OO )               ( OO ).                                             

// ,--.   ,--.).-'),-----. ,--. ,--.  .-'),-----. (_)---\_) ,--. ,--.     .-----.  ,-.-')  .-'),-----. 

// |   `.'   |( OO'  .-.  '|  .'   / ( OO'  .-.  '/    _ |  |  | |  |    '  .--./  |  |OO)( OO'  .-.  '

// |         |/   |  | |  ||      /, /   |  | |  |\  :` `.  |  | | .-')  |  |('-.  |  |  \/   |  | |  |

// |  |'.'|  |\_) |  |\|  ||     ' _)\_) |  |\|  | '..`''.) |  |_|( OO )/_) |OO  ) |  |(_/\_) |  |\|  |

// |  |   |  |  \ |  | |  ||  .   \    \ |  | |  |.-._)   \ |  | | `-' /||  |`-'| ,|  |_.'  \ |  | |  |

// |  |   |  |   `'  '-'  '|  |\   \    `'  '-'  '\       /('  '-'(_.-'(_'  '--'\(_|  |      `'  '-'  '

// """    """     """""""" """  """"      """""""  """""""  """"""""      """"""   """         """""""
// 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.7829583980106418x):
#include <bits/stdc++.h>



#define cn count

#define pb push_back

#define in insert

#define fs first

#define sc second

#define sz size

#define len length

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)

#define forni(i, n) for (ll i = 1; i < (ll) (n); ++i)

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



using namespace std;

using ll = long long;

const ll inf = 1e9+7; 

const double PI =  3.141592653589793;



int main(){

	IO;

	ll n,w,wi,vi;

	cin>>n>>w;

	ll dp[w+1];

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

	forn(i,n){

		cin>>wi>>vi;

		for(ll j = w-wi; j>=0; j--) dp[j+wi] = max(dp[j+wi],dp[j]+vi);

	}

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

	return 0;

}





// _   .-')                .-. .-')                 .-')                                               

//( '.( OO )_              \  ( OO )               ( OO ).                                             

// ,--.   ,--.).-'),-----. ,--. ,--.  .-'),-----. (_)---\_) ,--. ,--.     .-----.  ,-.-')  .-'),-----. 

// |   `.'   |( OO'  .-.  '|  .'   / ( OO'  .-.  '/    _ |  |  | |  |    '  .--./  |  |OO)( OO'  .-.  '

// |         |/   |  | |  ||      /, /   |  | |  |\  :` `.  |  | | .-')  |  |('-.  |  |  \/   |  | |  |

// |  |'.'|  |\_) |  |\|  ||     ' _)\_) |  |\|  | '..`''.) |  |_|( OO )/_) |OO  ) |  |(_/\_) |  |\|  |

// |  |   |  |  \ |  | |  ||  .   \    \ |  | |  |.-._)   \ |  | | `-' /||  |`-'| ,|  |_.'  \ |  | |  |

// |  |   |  |   `'  '-'  '|  |\   \    `'  '-'  '\       /('  '-'(_.-'(_'  '--'\(_|  |      `'  '-'  '

// """    """     """""""" """  """"      """""""  """""""  """"""""      """"""   """         """""""
// 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.765717635438269x):
#include <bits/stdc++.h>

#define fly ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define ll long long

const ll mod = 1e9 + 7;



using namespace std;

ll dp[100010][101] = {0};

int main(int argc, char const *argv[]) {

  fly;

  ll n,w;

  cin >> n >> w;

  vector<ll>weigth(n+1);

  vector<ll>cst(n+1);

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

    cin >> weigth[i] >> cst[i];

  }

  for(ll i = 0;i<=w;i++){

    for(ll j = 0;j<=n;j++){

      dp[i][j] = 0;

      if(i == 0 || j == 0)

        continue;

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

      if(i>=weigth[j]){

        dp[i][j] = max(dp[i][j], dp[i-weigth[j]][j-1] + cst[j]);

      }

    }

  }

  ll ans = 0;

  for(ll i = 0;i<=w;i++){

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

  }

  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.7658323627042418x):
#include <bits/stdc++.h>

#define fly ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define ll long long

const ll mod = 1e9 + 7;



using namespace std;

ll dp[100010][101] = {0};

int main(int argc, char const *argv[]) {

  fly;

  ll n,w;

  cin >> n >> w;

  vector<ll>weigth(n+1);

  vector<ll>cst(n+1);

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

    cin >> weigth[i] >> cst[i];

  }

  for(ll i = 0;i<=w;i++){

    for(ll j = 0;j<=n;j++){

      dp[i][j] = 0;

      if(i == 0 || j == 0)

        continue;

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

      if(i>=weigth[j]){

        dp[i][j] = max(dp[i][j], dp[i-weigth[j]][j-1] + cst[j]);

      }

    }

  }

  ll ans = 0;

  for(ll i = 0;i<=w;i++){

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

  }

  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.781101587221112x):
#include<bits/stdc++.h>

using namespace std;

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

#define  ll  long long

const int N=1e5+2;

ll d[102][N];

int main()

{

    ft

    ll t,i,j,n,m,l,r;

    cin>>n>>m;

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

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

    {

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

    }

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

    {

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

        {

            if(i==0 || j==0)

            {

                d[i][j]=0;

            }

            else if(w[i]>j)

            {

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

            }

            else

            {

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

            }

        }

    }

    cout<<d[n][m]<<"\n";

    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.7812173140572838x):
#include<bits/stdc++.h>

using namespace std;

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

#define  ll  long long

const int N=1e5+2;

ll d[102][N];

int main()

{

    ft

    ll t,i,j,n,m,l,r;

    cin>>n>>m;

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

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

    {

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

    }

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

    {

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

        {

            if(i==0 || j==0)

            {

                d[i][j]=0;

            }

            else if(w[i]>j)

            {

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

            }

            else

            {

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

            }

        }

    }

    cout<<d[n][m]<<"\n";

    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.7670039645278226x):
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;



ll dp[100005][105];    /// dp[x][i] = max sum of values for total weight x using 0....i weights



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);





    int n, W;

    cin>>n>>W;



    vector<int> weights(n), values(n);



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

        cin>>weights[i];

        cin>>values[i];

    }





    for(int w = 1; w<=W; w++){

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

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



            if(w >= weights[i])

                dp[w][i] = max(dp[w][i], dp[w-weights[i]][i-1] + values[i]);

        }

    }



    cout<<dp[W][n-1];





    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.767118775372855x):
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;



ll dp[100005][105];    /// dp[x][i] = max sum of values for total weight x using 0....i weights



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);





    int n, W;

    cin>>n>>W;



    vector<int> weights(n), values(n);



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

        cin>>weights[i];

        cin>>values[i];

    }





    for(int w = 1; w<=W; w++){

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

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



            if(w >= weights[i])

                dp[w][i] = max(dp[w][i], dp[w-weights[i]][i-1] + values[i]);

        }

    }



    cout<<dp[W][n-1];





    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.7828450166823557x):
#include<bits/stdc++.h>

#define MOD 1000000007

#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);

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

#define forr(i,a,b) for(i=a;i>b;i--)

#define mp make_pair

#define f first

#define s second

#define pb(x) push_back(x)

typedef  long long  int ll;

typedef std::vector<ll> vi;



#define input(vec,a,b) for(ll i =a;i<b;i++) cin>>vec[i]

#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" " ;cout<<endl;

#define all(a) a.begin(),a.end()

using namespace std;





void solve(){

        ll i,j , n,w,out;

        cin>>n>>w;

        ll we[n],v[n];

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

        {

                 cin>>we[i]>>v[i];

        }

        ll mv[n+1][w+1]={0};

        bool p[n+1][w+1]={0};

        

        for(i=0;i<=w;i++)

        {

                 mv[0][i]=0;

                 

        }

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

        {

                 mv[i][0]=0;

                 p[i][0]=1;

        }

        

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

        {

                 for(j=0;j<we[i-1];j++)

                 {

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

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

                 }

                 for(j=we[i-1];j<=w;j++)

                 {

                          if(p[i-1][j-we[i-1]])

                          {

                                   mv[i][j]=max(mv[i-1][j],mv[i-1][j-we[i-1]]+v[i-1]);

                                   p[i][j]=1;

                          }

                          else

                          {

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

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

                          }

                 }

        }

        out=0;

        for(i=w;i>=0;i--)

        {

              out=max(out,mv[n][i]);

        }

        cout<<out;

}



int main()

{

      IO;

      ll t=1;

      //cin>>t;





      while(t--)

      {



          solve();

      }

    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.782960856797622x):
#include<bits/stdc++.h>

#define MOD 1000000007

#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);

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

#define forr(i,a,b) for(i=a;i>b;i--)

#define mp make_pair

#define f first

#define s second

#define pb(x) push_back(x)

typedef  long long  int ll;

typedef std::vector<ll> vi;



#define input(vec,a,b) for(ll i =a;i<b;i++) cin>>vec[i]

#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" " ;cout<<endl;

#define all(a) a.begin(),a.end()

using namespace std;





void solve(){

        ll i,j , n,w,out;

        cin>>n>>w;

        ll we[n],v[n];

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

        {

                 cin>>we[i]>>v[i];

        }

        ll mv[n+1][w+1]={0};

        bool p[n+1][w+1]={0};

        

        for(i=0;i<=w;i++)

        {

                 mv[0][i]=0;

                 

        }

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

        {

                 mv[i][0]=0;

                 p[i][0]=1;

        }

        

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

        {

                 for(j=0;j<we[i-1];j++)

                 {

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

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

                 }

                 for(j=we[i-1];j<=w;j++)

                 {

                          if(p[i-1][j-we[i-1]])

                          {

                                   mv[i][j]=max(mv[i-1][j],mv[i-1][j-we[i-1]]+v[i-1]);

                                   p[i][j]=1;

                          }

                          else

                          {

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

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

                          }

                 }

        }

        out=0;

        for(i=w;i>=0;i--)

        {

              out=max(out,mv[n][i]);

        }

        cout<<out;

}



int main()

{

      IO;

      ll t=1;

      //cin>>t;





      while(t--)

      {



          solve();

      }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100+5;

const int maxw = 1e5+5;

long long dp[maxw];

int main(int argc, char const *argv[])

{

	int n, w;

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

	

	memset(dp, 0, sizeof dp);

	int x, v;

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

		scanf("%d%d", &x, &v);

		for(int j = w; j >= x; j--){

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

		}

	}



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

	return 0;

}

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

#define MOD 1000000007

#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);

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

#define forr(i,a,b) for(i=a;i>b;i--)

#define mp make_pair

#define f first

#define s second

#define pb(x) push_back(x)

typedef  long long  int ll;

typedef std::vector<ll> vi;



#define input(vec,a,b) for(ll i =a;i<b;i++) cin>>vec[i]

#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" " ;cout<<endl;

#define all(a) a.begin(),a.end()

using namespace std;





void solve(){

        ll i,j , n,w,out;

        cin>>n>>w;

        ll we[n],v[n];

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

        {

                 cin>>we[i]>>v[i];

        }

        ll mv[n+1][w+1]={0};

        bool p[n+1][w+1]={0};

        

        for(i=0;i<=w;i++)

        {

                 mv[0][i]=0;

                 

        }

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

        {

                 mv[i][0]=0;

                 p[i][0]=1;

        }

        

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

        {

                 for(j=0;j<we[i-1];j++)

                 {

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

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

                 }

                 for(j=we[i-1];j<=w;j++)

                 {

                          if(p[i-1][j-we[i-1]])

                          {

                                   mv[i][j]=max(mv[i-1][j],mv[i-1][j-we[i-1]]+v[i-1]);

                                   p[i][j]=1;

                          }

                          else

                          {

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

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

                          }

                 }

        }

        out=0;

        for(i=w;i>=0;i--)

        {

              out=max(out,mv[n][i]);

        }

        cout<<out;

}



int main()

{

      IO;

      ll t=1;

      //cin>>t;





      while(t--)

      {



          solve();

      }

    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.8072969745567968x):
#include <bits/stdc++.h>

using namespace std;

long long arr [110000];



int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

for (j = w - wi;j >= 0;j --)

{

arr [j + wi] = max (arr [j + wi] , arr [j] + vi);

}

}

long long t ;

t = 0;

for (i = 0 ; i <= w;i ++)

{

t = max (t , arr [i]);

}

cout <<t<<'\n';



}
// 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.8074144034347388x):
#include <bits/stdc++.h>

using namespace std;

long long arr [110000];



int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

for (j = w - wi;j >= 0;j --)

{

arr [j + wi] = max (arr [j + wi] , arr [j] + vi);

}

}

long long t ;

t = 0;

for (i = 0 ; i <= w;i ++)

{

t = max (t , arr [i]);

}

cout <<t<<'\n';



}