stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



namespace TYC

{

	typedef long long ll;

	typedef pair<int, int> pii;

	const int N = 505;



	int n, tot, mod, F[N][N];

	pii A[N];



	int solve(const int k)

	{

		memset(F, 0, sizeof(F));

		F[0][0] = 1;

		int c1 = 0, c2 = 0;

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

			if (A[i].second == 0)

			{

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

					F[i + 1][j] = int((ll)F[i][j] * (A[i].first + 1 - c1 - j) % mod);

				c1++;

			}

			else

			{

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

				{

					F[i + 1][j + 1] = int((F[i + 1][j + 1] + (ll)F[i][j] * (A[i].first + 1 - c1 - j) % mod) % mod);

					F[i + 1][j] = int((F[i + 1][j] + (ll)F[i][j] * (A[i].second + 1 - n - k - (c2 - j)) % mod) % mod);

				}

				c2++;

			}

		return F[tot][k];

	}



	void work()

	{

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

		tot = n << 1;

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

		{

			int l = int(ceil(sqrt((double)n * n - (double)i  * i)));

			int r = int(floor(sqrt((double)n * n * 4 - (double)i * i)));

			A[i] = {l - 1, min(tot - 1, r)};

		}

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

			A[i] = {int(floor(sqrt((double)n * n * 4 - (double)i * i))), 0};



		sort(A, A + tot);

		int ans = 0;

		for (int i = 0, d = 1; i <= n; i++, d = -d)

			ans = int(((ll)ans + d * solve(i) + mod) % mod);

		printf("%d\n", ans);

	}

}



int main()

{

	TYC::work();

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define re register int

#define F(x,y,z) for(re x=y;x<=z;x++)

#define FOR(x,y,z) for(re x=y;x>=z;x--)

typedef long long ll;

#define I inline void

#define IN inline int

#define C(x,y) memset(x,y,sizeof(x))

#define STS system("pause")

template<class D>I read(D &res){

	res=0;register D g=1;register char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')g=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		res=(res<<3)+(res<<1)+(ch^48);

		ch=getchar();

	}

	res*=g;

}

struct P{

	int p,id;

	friend bool operator < (P x,P y){

		return x.p==y.p?x.id>y.id:x.p<y.p;

	}

}a[510];

int n,m,ans,l[510],r[510],f[510][300];

int main(){

    read(n);read(m);

    F(i,0,(n<<1)-1){

    	a[i].id=i;r[i]=min((n<<1)-1,(int)floor(sqrt(4*n*n-i*i)));

    	if(i>=n)l[i]=0,a[i].p=r[i];

    	else {l[i]=ceil(sqrt(n*n-i*i));a[i].p=l[i]-1;}

	}

	sort(a,a+2*n);

	F(k,0,n){

		re cnt=0;C(f,0);f[0][0]=1;

		F(i,1,n<<1){

			if(a[i-1].id<n)cnt++;

			F(j,0,min(k,cnt)){

				if(a[i-1].id<n){

					f[i][j]=(ll)f[i-1][j]*(r[a[i-1].id]+1-(2*n-1-a[i-1].id+k-j))%m;

					if(j)(f[i][j]+=(ll)f[i-1][j-1]*(a[i-1].p+1-(i-1-(cnt-j)))%m)%=m;

				}

				else f[i][j]=(ll)f[i-1][j]*(a[i-1].p+1-(i-1-(cnt-j)))%m;

			}

		}

		if(k&1)(ans-=f[2*n][k]-m)%=m;

		else (ans+=f[2*n][k])%=m;

	}

	if(ans<0)(ans%=m)+=m;

	printf("%d",ans);

   	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#define cri const int

#define ll long long

using namespace std;

int dp[502][502],ans;

pair<int,int>f[502];

inline int read(int x=0){ scanf("%d",&x);return x; }

int main(){

	cri n=read(),mod=read();

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

		if(i>=n) f[i]=make_pair((int)sqrt(4*n*n-i*i)+1,0);

		else f[i]=make_pair((int)(sqrt(n*n-i*i-1e-7))+1,(int)sqrt(4*n*n-i*i)+(i!=0));

	}

	sort(f,f+n+n);

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

		int c1=0,c2=0;

		memset(dp,0,sizeof dp);

		dp[0][0]=1;

		for(int i=0;i<n+n;!f[i].second?c1++:c2++,i++)

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

				if(!f[i].second) dp[i+1][j]=(dp[i+1][j]+1ll*dp[i][j]*(f[i].first-j-c1))%mod;

				else{

					if(j<k) dp[i+1][j+1]=(dp[i+1][j+1]+1ll*dp[i][j]*(f[i].first-j-c1))%mod;

					dp[i+1][j]=(dp[i+1][j]+1ll*dp[i][j]*(f[i].second-n-k-(c2-j)))%mod;

				}

			}

		if(k&1) ans=(ans-dp[n+n][k]+mod)%mod;

		else ans=(ans+dp[n+n][k])%mod;

	}

	cout<<ans<<endl;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define re register int

#define F(x,y,z) for(re x=y;x<=z;x++)

#define FOR(x,y,z) for(re x=y;x>=z;x--)

typedef long long ll;

#define I inline void

#define IN inline int

#define C(x,y) memset(x,y,sizeof(x))

#define STS system("pause")

template<class D>I read(D &res){

	res=0;register D g=1;register char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')g=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		res=(res<<3)+(res<<1)+(ch^48);

		ch=getchar();

	}

	res*=g;

}

struct P{

	int p,id;

	friend bool operator < (P x,P y){

		return x.p==y.p?x.id>y.id:x.p<y.p;

	}

}a[510];

int n,m,ans,l[510],r[510],f[510][300];

int main(){

    read(n);read(m);

    F(i,0,(n<<1)-1){

    	a[i].id=i;r[i]=min((n<<1)-1,(int)floor(sqrt(4*n*n-i*i)));

    	if(i>=n)l[i]=0,a[i].p=r[i];

    	else {l[i]=ceil(sqrt(n*n-i*i));a[i].p=l[i]-1;}

	}

	sort(a,a+2*n);

	F(k,0,n){

		re cnt=0;C(f,0);f[0][0]=1;

		F(i,1,n<<1){

			if(a[i-1].id<n)cnt++;

			F(j,0,min(k,cnt)){

				if(a[i-1].id<n){

					f[i][j]=(ll)f[i-1][j]*(r[a[i-1].id]+1-(2*n-1-a[i-1].id+k-j))%m;

					if(j)(f[i][j]+=(ll)f[i-1][j-1]*(a[i-1].p+1-(i-1-(cnt-j)))%m)%=m;

				}

				else f[i][j]=(ll)f[i-1][j]*(a[i-1].p+1-(i-1-(cnt-j)))%m;

			}

		}

		if(k&1)(ans-=f[2*n][k]-m)%=m;

		else (ans+=f[2*n][k])%=m;

	}

	if(ans<0)(ans%=m)+=m;

	printf("%d",ans);

   	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

int n,m,mod,l[525],r[525];

ll f[525][252],ans;

pair<int,int> a[525]; 

inline ll calc(int k){

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

	int c1=0,c2=0; f[0][0]=1;

	for(int i=1;i<=m;c1+=(a[i].second==0),c2+=(a[i].second!=0),++i) for(int j=0;j<=i&&j<=k;++j){

		if(a[i].second==0) (f[i][j]+=f[i-1][j]*(a[i].first-c1-j))%=mod; 

		else{

			if(j) (f[i][j]+=f[i-1][j-1]*(a[i].first-j-c1+1))%=mod;

			(f[i][j]+=f[i-1][j]*(a[i].second-k-n-(c2-j)))%=mod;

		}

	}

	return f[m][k];

}

int main(){

	cin>>n>>mod; m=n<<1;

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

		l[i]=0; r[i]=m-1;

		while(l[i]<m&&l[i]*l[i]+i*i<n*n) ++l[i];

		while(r[i]>0&&r[i]*r[i]+i*i>m*m) --r[i];

		--l[i];

		if(i<n) a[i+1]=make_pair(l[i]+1,r[i]+1);

		else a[i+1]=make_pair(r[i]+1,0);

	}

	sort(a+1,a+m+1);

	for(int i=0;i<=n;++i) (ans+=((i&1)?-1:1)*calc(i))%=mod;

	cout<<(ans%mod+mod)%mod<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

#define re register int

#define F(x,y,z) for(re x=y;x<=z;x++)

#define FOR(x,y,z) for(re x=y;x>=z;x--)

typedef long long ll;

#define I inline void

#define IN inline int

#define C(x,y) memset(x,y,sizeof(x))

#define STS system("pause")

template<class D>I read(D &res){

	res=0;register D g=1;register char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')g=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		res=(res<<3)+(res<<1)+(ch^48);

		ch=getchar();

	}

	res*=g;

}

struct P{

	int p,id;

	friend bool operator < (P x,P y){

		return x.p==y.p?x.id>y.id:x.p<y.p;

	}

}a[510];

int n,m,ans,l[510],r[510],f[510][300];

int main(){

    read(n);read(m);

    F(i,0,(n<<1)-1){

    	a[i].id=i;r[i]=min((n<<1)-1,(int)floor(sqrt(4*n*n-i*i)));

    	if(i>=n)l[i]=0,a[i].p=r[i];

    	else {l[i]=ceil(sqrt(n*n-i*i));a[i].p=l[i]-1;}

	}

	sort(a,a+2*n);

	F(k,0,n){

		re cnt=0;C(f,0);f[0][0]=1;

		F(i,1,n<<1){

			if(a[i-1].id<n)cnt++;

			F(j,0,min(k,cnt)){

				if(a[i-1].id<n){

					f[i][j]=(ll)f[i-1][j]*(r[a[i-1].id]+1-(2*n-1-a[i-1].id+k-j))%m;

					if(j)(f[i][j]+=(ll)f[i-1][j-1]*(a[i-1].p+1-(i-1-(cnt-j)))%m)%=m;

				}

				else f[i][j]=(ll)f[i-1][j]*(a[i-1].p+1-(i-1-(cnt-j)))%m;

			}

		}

		if(k&1)(ans-=f[2*n][k]-m)%=m;

		else (ans+=f[2*n][k])%=m;

	}

	if(ans<0)(ans%=m)+=m;

	printf("%d",ans);

   	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int N=510;

typedef long long ll;

int dp[N/2][N],mod,jc[N],n,L[N],R[N],ans,id[N];

int main(){

	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n>>mod;

	jc[0]=1;

	for(int i=1;i<=2*n;++i)jc[i]=(ll)jc[i-1]*i%mod;

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

		for(L[i]=0;i*i+L[i]*L[i]<n*n;++L[i]);

		for(R[i]=1;i*i+(2*n-R[i])*(2*n-R[i])>2*n*2*n;++R[i]);--R[i];

		id[i]=i;

	}

	for(int i=n;i<2*n;++i)L[i]=2*n-R[i];

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

		for(int j=i+1;j<2*n;++j)

			if(L[i]<L[j]||(L[i]==L[j]&&R[i]>R[j])){swap(L[i],L[j]);swap(R[i],R[j]);swap(id[i],id[j]);}

	for(int i=n;i<=2*n;++i){

		memset(dp,0,sizeof dp);dp[0][0]=1;

		int cnt=0,lim1=0,lim2=0;

		for(int j=0;j<2*n;++j)if(id[j]>=n){

			++cnt;lim1=min(lim1+1,i);

			for(int l=lim2;l>=0;--l){

				for(int k=lim1;k>=cnt;--k)

					dp[l][k]=dp[l][k-1]?(ll)dp[l][k-1]*(L[j]-(i-k))%mod:0;

				dp[l][cnt-1]=0;

			}

		}else{

			lim1=min(lim1+1,i);lim2=min(lim2+1,2*n-i);

			for(int l=lim2;l>=0;--l)for(int k=lim1;k>=cnt;--k)

				{

					if(dp[l][k-1])dp[l][k]=(dp[l][k]+(ll)dp[l][k-1]*(L[j]-(i-k)))%mod;

					if(l&&dp[l-1][k])dp[l][k]=(dp[l][k]+(ll)dp[l-1][k]*(R[j]-l+1))%mod;

				}

		}

		for(int j=0;j<=2*n-i;++j){

			int ret=(ll)dp[j][i]*jc[2*n-i-j]%mod;

			if((i-n+j)&1)ans=(ans-ret+mod)%mod;

			else ans=(ans+ret)%mod;

		}

	}

	cout<<ans<<'\n';

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

const int N=510;

typedef long long ll;

int dp[N],mod,jc[N],n,L[N],R[N],ans,id[N];

int main(){

	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n>>mod;

	jc[0]=1;

	for(int i=1;i<=2*n;++i)jc[i]=(ll)jc[i-1]*i%mod;

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

		for(L[i]=0;i*i+L[i]*L[i]<n*n;++L[i]);

		for(R[i]=2*n-1;i*i+R[i]*R[i]>2*n*2*n;--R[i]);

		id[i]=i;

	}

	for(int i=n;i<2*n;++i)L[i]=R[i]+1;

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

		for(int j=i+1;j<2*n;++j)

			if(L[i]>L[j]||(L[i]==L[j]&&R[i]>R[j])){swap(L[i],L[j]);swap(R[i],R[j]);swap(id[i],id[j]);}

	for(int i=n;i<=2*n;++i){

		memset(dp,0,sizeof dp);dp[0]=1;

		int cnt=0,lim1=0;

		for(int j=0;j<2*n;++j)if(id[j]>=n){

			++cnt;lim1=min(lim1+1,i);

			for(int k=lim1;k>=cnt;--k)

				dp[k]=dp[k-1]?(ll)dp[k-1]*(L[j]-k+1)%mod:0;

			dp[cnt-1]=0;

		}else{

			lim1=min(lim1+1,i);

			for(int k=lim1;k>cnt;--k)dp[k]=((ll)dp[k]*(R[j]-(i+j-k)+1)+(ll)dp[k-1]*(L[j]-k+1))%mod;

			dp[cnt]=(ll)dp[cnt]*(R[j]-(i+j-cnt)+1)%mod;

		}

		if((i-n)&1)ans=(ans-dp[i]+mod)%mod;

		else ans=(ans+dp[i])%mod;

	}

	cout<<ans<<'\n';

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
///Bismillahir Rahmanir Rahim

#include "bits/stdc++.h"



#define                           ll                          long long

#define                           int                         ll

#define                           fi                          first

#define                           si                          second

#define                           mp                          make_pair

#define                           pb                          push_back

#define                           pi                          pair<ll,ll>

#define                           clr(x)                      memset(x,0,sizeof(x));

#define                           f(i,l,r)                    for(int i=l;i<=r;i++)

#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)

#define                           done(i)                     cout<<"done = "<<i<<endl;

#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;

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



using namespace std;



const ll inf=1e18;

const int mod=1e9+7;

const int M=200005;

int a[M],n,k,cnt[M];

void work()

{

   clr(cnt);

   f(i,1,n)

   {

       int d=a[i];

       int lft=i-d;

       int rgt=i+d;

       lft=max(lft,1LL);

       rgt=min(rgt,n);

       if(lft>rgt)continue;

       cnt[lft]++;

       cnt[rgt+1]--;

   }

   f(i,1,n)

   {

       cnt[i]+=cnt[i-1];

   }

   f(i,1,n)

   {

       a[i]=cnt[i];

   }

}

 main()



{

    fast

    cin>>n>>k;

    f(i,1,n)

    {

        cin>>a[i];

    }

    int tmp=1000;

    tmp=min(tmp,k);

    while(tmp--)

    {

        work();

    }

    f(i,1,n)

    {

        cout<<a[i]<<" ";

    }

    cout<<endl;

    return 0;



}








































































// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <vector>

#include <cmath>

#include <string>

#include <set>

#include <map>

#include <unordered_map>

#include <iomanip>

#include <stack>

#include <queue>

#include <deque>

using namespace std;

 

long long mod = 1000000007;

const long long N=2e5+10;



int a[N],b[2*N];

int main() {

    

    long long n, k;

    

    cin>>n>>k;

    

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

        cin>>a[i];

    }

    k=min(k, 1ll + 50);

    

    while(k--){

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

            b[i]=0;

        }

        

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

            int l = max(1,i-a[i]);

            int r = i + a[i];

            

            b[l]++;

            b[r+1]--;

        }

        

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

            

            b[i]=b[i]+b[i-1];

        

        }

        

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

            a[i]=b[i];

        }

    }

    

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

        cout<<a[i]<<' ';

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <map>

#include <algorithm>

#define FOR(i,l,r) for (i=l;i<=r;i++)

#define INF 0x3f3f3f3f



using namespace std;



int i,j,k,l,m,n;

static int c[5][6],t[30],z[6];

const int w[24][6]={2,3,0,5,4,1, 3,2,0,5,1,4, 4,1,0,5,3,2, 1,4,0,5,2,3,

	2,3,1,4,0,5, 3,2,1,4,5,0, 0,5,1,4,3,2, 5,0,1,4,2,3, 

	5,0,2,3,4,1, 0,5,2,3,1,4, 4,1,2,3,0,5, 1,4,2,3,5,0,

	5,0,3,2,1,4, 0,5,3,2,4,1, 1,4,3,2,0,5, 4,1,3,2,5,0,

	2,3,4,1,5,0, 3,2,4,1,0,5, 5,0,4,1,3,2, 0,5,4,1,2,3,

	2,3,5,0,1,4, 3,2,5,0,4,1, 1,4,5,0,3,2, 4,1,5,0,2,3};

string st;

int dfs(int o)

{

	int ans=INF,i,j,k;

	if (o>n)

	{

		ans=0;

		FOR(i,0,5)

		{

			memset(t,0,sizeof(t));

			int ma=0;

			FOR(j,0,n)

				ma=max(ma,++t[c[j][w[z[j]][i]]]);

			ans+=(n-ma);

		}

		return ans;

	}

	FOR(i,0,23)

	{

		z[o]=i;

		ans=min(ans,dfs(o+1));

	}

	return ans;   

}

int main() {

	map <string,int> a;

	while (scanf("%d",&n)!=EOF && n)

	{

		FOR(i,1,n) FOR(j,0,5) {

		cin>>st;if (!a[st]) a[st]=++m;

		c[i][j]=a[st];} 

		z[1]=0;

		printf("%d\n",dfs(2));

		map<string,int>::iterator o=a.begin();

		for (;o!=a.end();o++)

			o->second=0;

		m=0;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
int dice24[24][6]=

{

	{2,1,5,0,4,3},{2,0,1,4,5,3},{2,4,0,5,1,3},{2,5,4,1,0,3},{4,2,5,0,3,1},

	{5,2,1,4,3,0},{1,2,0,5,3,4},{0,2,4,1,3,5},{0,1,2,3,4,5},{4,0,2,3,5,1},

	{5,4,2,3,1,0},{1,5,2,3,0,4},{5,1,3,2,4,0},{1,0,3,2,5,4},{0,4,3,2,1,5},

	{4,5,3,2,0,1},{1,3,5,0,2,4},{0,3,1,4,2,5},{4,3,0,5,2,1},{5,3,4,1,2,0},

	{3,4,5,0,1,2},{3,5,1,4,0,2},{3,1,0,5,4,2},{3,0,4,1,5,2},

};

#include<cstdio>

#include<cstring>

#include<string>

#include<vector>

#include<algorithm>

using namespace std;



const int maxn=4;

int n,dice[maxn][6],ans;



vector<string> names;

int  ID(const char* name)

{

	string s(name);

	int n=names.size();

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

	if (names[i]==s) return i;

	names.push_back(s);

	return n;

}



int r[maxn],color[maxn][6];



void check()

{

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

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

		color[i][dice24[r[i]][j]]=dice[i][j];

	int tot=0;

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

	{

		int cnt[maxn*6];

		memset(cnt,0,sizeof(cnt));

		int maxface=0;

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

			maxface=max(maxface,++cnt[color[i][j]]);

		tot+=n-maxface;

	}

	ans=min(ans,tot);

}



void dfs(int d)

{

	if (d==n) check();

	else for(int i=0;i<24;i++)

	{

		r[d]=i;

		dfs(d+1);

	}

}

int main()

{

	while (scanf("%d",&n)==1&&n)

	{

		names.clear();

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

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

			{

				char name[30];

				scanf("%s",name);

				dice[i][j]=ID(name);

			}

		ans=n*6;

		r[0]=0;

		dfs(1);

		printf("%d\n",ans);

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):




#include<bits/stdc++.h>

using namespace std;

#define MAX 100005

#define INF (1e9+1)

 

int n,W;

int dp[MAX];

 

int main(){

  fill(dp,dp+MAX,-INF);

  dp[0]=0;

   

  cin>>n>>W;

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

    int v,w,m;

    cin>>v>>w>>m;

 

    for(int k=0;m>0;k++){

      int key= min( m, (1<<k) );

      m-=key;

 

      int nv=key*v;

      int nw=key*w;

      for(int j=W;j>=nw;j--){

        dp[j]=max(dp[j],dp[j-nw]+nv);

      }

 

 

    }

     

  }

  int ans=0;

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

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

  cout<<ans<<endl;

  return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

 

using namespace std;

 

const int INF = 1 << 30;

 

int main()

{

  int N, W;

  int dp[10001] = {}, deq[10001], deqv[10001];

 

  cin >> N >> W;

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

    int v, w, m;

    cin >> v >> w >> m;

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

      int s = 0, t = 0;

      for(int l = 0; l * w + k <= W; l++) {

        int val = dp[l * w + k] - l * v;

        while(s < t && deqv[t - 1] <= val) --t;

        deq[t] = l;

        deqv[t++] = val;

        dp[l * w + k] = deqv[s] + l * v;

        if(deq[s] == l - m) ++s;

      }

    }

  }

 

  cout << dp[W] << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ll long long

#define INF 999999999

#define MOD 1000000007

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



using namespace std;



typedef pair<int,int>P;



const int MAX_N = 100005;



int dp[MAX_N];



int main()

{

	int n,W;

	int v,w,m;

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

	fill(dp,dp+MAX_N,-INF);

	dp[0] = 0;

	rep(i,n){

		scanf("%d%d%d",&v,&w,&m);

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

			int hoge = min(m,(1<<j));

			m-=hoge;

			for(int k=W;k>=hoge*w;k--){

				dp[k] = max(dp[k],dp[k-hoge*w]+hoge*v);

			}

		}

	}

	cout << *max_element(dp,dp+W+1) << "\n";

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define ll long long

#define INF 999999999

#define MOD 1000000007

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



using namespace std;



typedef pair<int,int>P;



const int MAX_N = 100;

const int MAX_W = 10000;



int n,W;

int w[MAX_N];

int v[MAX_N];

int m[MAX_N];

int dp[MAX_W+1];

int deq[MAX_W+1];

int deqv[MAX_W+1];



int main()

{

	cin >> n >> W;

	rep(i,n){

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

	}

	rep(i,n){

		rep(a,w[i]){

			int s=0,t=0;

			for(int j=0;j*w[i]+a<=W;j++){

				int val = dp[j*w[i]+a]-j*v[i];

				while(s<t&&deqv[t-1]<=val){

					t--;

				}

				deq[t] = j;

				deqv[t++] = val;

				dp[j*w[i]+a] = deqv[s] + j*v[i];

				if(deq[s] == j-m[i]){

					s++;

				}

			}

		}

	}

	cout << dp[W] << "\n";

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<string>

#include<vector>

#include<map>

#include<stack>

#include<queue>



using namespace std;

#define MAX 100005

static const int INF=1<<19;



int main(){

	int N,W;

	int dp[MAX];

	int ans=0;

	

	fill(dp,dp+MAX,-INF);

	dp[0]=0;

	

	scanf("%d %d",&N,&W);

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

		int v,w,m;

		scanf("%d %d %d",&v,&w,&m);

		for(int k=0;m>0;k++){

			int key=min(m,(1<<k));

			m-=key;

			for(int j=W;j>=key*w;j--){

				dp[j]=max(dp[j],dp[j-key*w]+key*v);

			}

		}

	}

	for(int i=0;i<=W;i++) ans=max(ans,dp[i]);

	printf("%d\n",ans);

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<string>

#include<vector>

#include<map>

#include<stack>

#include<queue>



using namespace std;



int main(){

	int N,W;

	

	scanf("%d %d",&N,&W);

	vector<int> dp(W+1,0);

	

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

		int v,w,m;

		scanf("%d %d %d",&v,&w,&m);

		for(int k=0;m>0;k++){

			int key=min(m,(1<<k));

			m-=key;

			for(int j=W;j>=key*w;j--){

				dp[j]=max(dp[j],dp[j-key*w]+key*v);

			}

		}

	}

	

	int ans=0;

	for(int i=0;i<=W;i++) ans=max(ans,dp[i]);

	printf("%d\n",ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include<vector>

#include<stack>

using namespace std;

static const int MAXN=100000;

static const int NIL=-1;

 vector<int>G[MAXN];

 int color[MAXN];

 int n;

 void dfs(int r,int c)

 {

      stack<int>S;

      S.push(r);

      color[r]=c;

      while(!S.empty()){

        int u=S.top();S.pop();

            for(int i=0;i<G[u].size();i++){

                int v=G[u][i];

                if(color[v]==NIL){

                    color[v]=c;

                    S.push(v);

                }

            }

      }

 }

 void assignColor()

 {

     int id=1;

     for(int i=0;i<n;i++)color[i]=NIL;

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

        if(color[u]==NIL)dfs(u,id++);

     }

 }

int main()

{

    int b,q;

    cin>>n>>b;

    int s,t;

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

        cin>>s>>t;

        G[s].push_back(t);

        G[t].push_back(s);

    }

    assignColor();

    cin>>q;

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

        cin>>s>>t;

        if(color[s]==color[t]){

            cout<<"yes"<<endl;

        }else{

        cout<<"no"<<endl;

        }

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#pragma GCC optimize("03")

#include <bits/stdc++.h>

#define endl '\n'

#define ll long long 

using namespace std;

int f[200000];

int find(int x){

	if(f[x]==x)

		return x;

	else

		return f[x]=find(f[x]);

}

void merge(int c,int d){

	f[d]=c;

}

int main()

{

    ios::sync_with_stdio(0);cin .tie(NULL);

    ll a,b,num;

   	cin >> a >> b;

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

	f[i]=i;

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

    {

    	ll c,d;

    	cin >> c >> d;

    	c=find(c);

    	d=find(d);

   		merge(c,d);

	}

	cin >> num;

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

	{

		ll e,g;

		cin >> e >> g;

		if(find(e)==find(g))

			cout << "yes" << endl;

		else

			cout << "no" << endl;

	}

}


// Fastest known solution for this problem: