#include #define int ll using namespace std; #define rep(i,n) for(int i=0;i=0;i--) #define rng(i,c,n) for(int i=c;i #define _3PawRSC ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using vi=vector; using pii=pair; void print(){cout<<'\n';} template void print(const h&v,const t&...u){cout<>n>>k; int seed,a,b,m; cin>>seed>>a>>b>>m; vi w(n),c(n); { vi f(2*n); f[0]=seed; rng(i,1,2*n){ f[i]=(f[i-1]*a+b)%m; } rep(i,n){ w[i]=f[i]%3+1; } rep(i,n){ c[i]=w[i]*f[i+n]; } } vec(vi) rbts(3); rep(i,n){ rbts[w[i]-1].pb(c[i]); // print(w[i],c[i]); } rep(v,3){ sort(rbts[v].begin(), rbts[v].end()); } int si=sz(rbts[0]),si1=sz(rbts[1]),si2=sz(rbts[2]); vi ps; rep(i,si){ ps.pb((!sz(ps)?0:ps.back())+rbts[0][i]); } vi ps1; rep(i,si1){ ps1.pb((!sz(ps1)?0:ps1.back())+rbts[1][i]); } auto range_sum=[&](vi&ps,int l,int r)->int{ if(l>r) return 0; // print(l,r); if(l<=0) l=0; return ps[r]-(!l?0:ps[l-1]); }; // range_sum(ps,si-1) auto af=[&](int x,int take)->int{ int now=range_sum(ps,si-1-take+1,si-1)+range_sum(ps1,si1-1-take+1,si1-1); int leftover=(x-take)*3; if(si-1-take>=0){ now+=range_sum(ps,si-1-take-leftover+1,si-1-take); } return now; }; // print(af(1,1)); auto ask=[&](int x)->int{ int l=0,r=min(x,max(si,si1)); while(r-l>3){ int ml=(2*l+r)/3; int mr=(l+2*r)/3; int fl=af(x,ml); int fr=af(x,mr); if(fl>fr){ r=mr; }else{ l=ml; } } int ret=0; rng(i,l,r+1){ // print(x,i,af(x,i)); ret=max(ret,af(x,i)); } return ret; }; // print(ask(1)); int ans=0,ad=0; rep(i,min(k,si2)+1){ ans=max(ans,ask(k-i)+ad); if(i