Tinder

#include <iostream>
#define N 5005
using namespace std;
int n,gmax,i,j,v[N],g[N],t,h;
long long a[2][N*2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>n>>gmax ;
    for(i=1;i<=n;++i)
        cin>>v[i]>>g[i];
    for(i=1;i<=n;++i)
    {
        if(i%2==0)
            t=1,h=0;
        else
            t=0,h=1;
        for(j=1;j<=gmax;++j)
            if(j>=g[i])
                a[h][j]=max(a[t][j],a[t][j-g[i]]+v[i]);
            else
                a[h][j]=a[t][j];
    }
	cout<<a[n%2][gmax];
    return 0;
}