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

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<map>

#include<queue>

#include<set>

#include<vector>

#include<bitset>

#define int long long

#define lowbit(x) ((x)&(-x))

using namespace std;

const int maxn=3005,mod=1e9+7,niyuan=5e8+4;

int n,q,dp[maxn][maxn],a[maxn],ans;

inline int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

		if(ch=='-')

			f=-1;

		ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

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

		ch=getchar();

    }

    return x*f;

}

inline void write(int a)

{

    if(a<0)

    {

		putchar('-');

		putchar('1');

    }

    else

    {

		if(a>=10)

			write(a/10);

		putchar(a%10+'0');

    }

}

signed main()

{

	n=read(),q=read();

	int tmp=1;

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

		tmp=tmp*2%mod;

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

		a[i]=read();

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

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

			dp[i][j]=tmp*(a[i]>a[j]);

//	for(int i=1;i<=n;++i,cout<<endl)

//		for(int j=1;j<=n;++j)

//			cout<<dp[i][j]<<' ';

	while(q--)

	{

		int x=read(),y=read();

		if(x>y)

			swap(x,y);

		int xi[maxn],yi[maxn],ix[maxn],iy[maxn];

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

			xi[i]=dp[x][i],yi[i]=dp[y][i],ix[i]=dp[i][x],iy[i]=dp[i][y];

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

			if(i!=x&&i!=y)

			{

				dp[i][x]=ix[i]*niyuan%mod+iy[i]*niyuan%mod;

				dp[i][y]=ix[i]*niyuan%mod+iy[i]*niyuan%mod;

				dp[x][i]=xi[i]*niyuan%mod+yi[i]*niyuan%mod;

				dp[y][i]=xi[i]*niyuan%mod+yi[i]*niyuan%mod;

			}

		dp[y][x]=dp[x][y]=xi[y]*niyuan%mod+yi[x]*niyuan%mod;

//		for(int i=1;i<=n;++i,cout<<endl)

//			for(int j=1;j<=n;++j)

//				cout<<dp[i][j]<<' ';

	}

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

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

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

	write(ans);

    return 0;

}


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



const int _ = 3e3 + 5, p = 1e9 + 7;



int n, m, a[_], dp[_][_];



inline int power(int x, int k) {

    int res = 1;

    for (; k; k >>= 1, x = 1ll * x * x % p)

        if (k & 1) res = 1ll * res * x % p;

    return res % p;

}



int main() {

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

    for (int i = 1; i <= n; ++i) scanf("%d", a + i);

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

        for (int j = 1; j <= n; ++j) dp[i][j] = a[i] < a[j];

    int inv2 = power(2, p - 2);

    for (int x, y, i = 1; i <= m; ++i) {

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

        dp[x][y] = dp[y][x] = 1ll * inv2 * ((dp[x][y] + dp[y][x]) % p) % p;

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

            if (j == x | j == y) continue ;

            dp[x][j] = dp[y][j] = 1ll * inv2 * ((dp[x][j] + dp[y][j]) % p) % p;

            dp[j][x] = dp[j][y] = 1ll * inv2 * ((dp[j][x] + dp[j][y]) % p) % p;

        }

    }

    int ans = 0;

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

        for (int j = 1; j < i; ++j) ans = (ans + dp[i][j]) % p;

    ans = 1ll * ans * power(2, m) % p;

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

    return 0;

}
// Slower C++ solution:
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int mod=1e9+7;

const int inv2=(mod+1)/2;

int qpow(int a,int b) { int c=1;

    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;

    return c;

}



const int N=3000+10;



int n,q,a[N],x[N],y[N],dp[N][N];



int main() {

    n=read(),q=read();

    for (int i=1;i<=n;++i) a[i]=read();

    for (int i=1;i<=q;++i) x[i]=read(),y[i]=read();

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

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

            dp[i][j]=a[i]>a[j];

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

        int u=x[i],v=y[i];

        dp[u][v]=dp[v][u]=1ll*(dp[u][v]+dp[v][u])*inv2%mod;

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

            if (j==u||j==v) continue;

            dp[u][j]=dp[v][j]=1ll*(dp[u][j]+dp[v][j])*inv2%mod;

            dp[j][u]=dp[j][v]=1ll*(dp[j][u]+dp[j][v])*inv2%mod;

        }

    }

    int ans=0;

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

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

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

    printf("%lld\n",1ll*ans*qpow(2,q)%mod);

    return 0;

}

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



const int _ = 3e3 + 5, p = 1e9 + 7;



int n, m, a[_], dp[_][_];



inline int power(int x, int k) {

    int res = 1;

    for (; k; k >>= 1, x = 1ll * x * x % p)

        if (k & 1) res = 1ll * res * x % p;

    return res % p;

}



int main() {

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

    for (int i = 1; i <= n; ++i) scanf("%d", a + i);

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

        for (int j = 1; j <= n; ++j) dp[i][j] = a[i] < a[j];

    int inv2 = power(2, p - 2);

    for (int x, y, i = 1; i <= m; ++i) {

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

        dp[x][y] = dp[y][x] = 1ll * inv2 * ((dp[x][y] + dp[y][x]) % p) % p;

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

            if (j == x | j == y) continue ;

            dp[x][j] = dp[y][j] = 1ll * inv2 * ((dp[x][j] + dp[y][j]) % p) % p;

            dp[j][x] = dp[j][y] = 1ll * inv2 * ((dp[j][x] + dp[j][y]) % p) % p;

        }

    }

    int ans = 0;

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

        for (int j = 1; j < i; ++j) ans = (ans + dp[i][j]) % p;

    ans = 1ll * ans * power(2, m) % p;

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

    return 0;

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

using namespace std;

typedef long long LL;



const int N=3e3+100,mod=1e9+7,inv2=(mod+1)>>1;

int n,Q,a[N],f[N][N],fx[N],gx[N],Ans;

void Inc(int &x,int y) {x+=y, x=x>=mod?x-mod:x;}

int qpow(LL x,int y)

{

	LL ret=1;

	while(y)

	{

		if(y&1) ret=ret*x%mod;

		x=x*x%mod, y>>=1;

	}

	return ret;

}



int main()

{

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

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

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

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

			f[i][j]=(a[i]>a[j])?1:0;

	for(int q=1;q<=Q;++q)

	{

		int x,y; scanf("%d%d",&x,&y);

		if(x == y) continue;

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

			fx[i]=1ll*inv2*(f[x][i]+f[y][i])%mod,

			gx[i]=1ll*inv2*(f[i][x]+f[i][y])%mod;

		fx[y]=1ll*inv2*(f[x][y]+f[y][x])%mod;

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

			f[x][i]=fx[i], f[i][x]=gx[i],

			f[y][i]=fx[i], f[i][y]=gx[i];

		f[x][y]=f[y][x]=fx[y], f[x][x]=f[y][y]=0;

	}

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

		for(int j=i+1;j<=n;++j) Inc(Ans,f[i][j]);

	Ans=1ll*Ans*qpow(2,Q)%mod; printf("%d",Ans);

	return 0;

}

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

typedef long long ll;

inline int rd(){

    int x=0,p=1;

    char a=getchar();

    while((a<48||a>57)&&a!='-')a=getchar();

    if(a=='-')p=-p,a=getchar();

    while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar();

    return x*p;

}

const int N=3002;

const ll mod=1e9+7;

int n,q;

int a[N];

ll f[N][N],ans;

inline ll fpow(ll b,ll p=mod-2){

	ll ans=1,tmp=b;

	while(p){

		if(p&1)ans=ans*tmp%mod;

		tmp=tmp*tmp%mod;

		p>>=1;

	}

	return ans;

}

int main(){

	n=rd(),q=rd();

	for(int i=1;i<=n;i++)a[i]=rd();

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

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

			f[i][j]=a[i]<a[j];

	ll inv=fpow(2);

	for(int i=1,x,y;i<=q;i++){

		x=rd(),y=rd();

		f[x][y]=f[y][x]=(f[x][y]+f[y][x])%mod*inv%mod;

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

			if(j!=x&&j!=y){

				f[x][j]=f[y][j]=(f[x][j]+f[y][j])%mod*inv%mod;

				f[j][x]=f[j][y]=(f[j][x]+f[j][y])%mod*inv%mod;

			}

	}

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

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

			ans=(ans+f[i][j])%mod;

	printf("%lld\n",ans*fpow(2,q)%mod);

    return 0;

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

#include <cstdio>

#include <cstring>

#define ll long long

const int MAXN = 1e5 + 7;

const ll p = 1e9 + 7;

const ll inv2 = 500000004ll;

ll n, m;

ll a[MAXN];

struct rec

{

    int x, y;

} q[MAXN];

ll f[3500][3500];



inline ll ksm(ll x, ll y)

{

    ll ans = 1;

    while (y)

    {

        if (y & 1)

            ans = ans * x % p;

        x = x * x % p;

        y >>= 1;

    }

    return ans;

}



int main()

{

    scanf("%lld%lld", &n, &m);

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

    {

        scanf("%lld", &a[i]);

    }

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

    {

        scanf("%lld%lld", &q[i].x, &q[i].y);

    }

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

    {

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

        {

            f[i][j] = a[i] < a[j];

        }

    }

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

    {

        f[q[i].x][q[i].y] = f[q[i].y][q[i].x] = inv2 * (f[q[i].x][q[i].y] + f[q[i].y][q[i].x]) % p;

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

        {

            if (j != q[i].x && j != q[i].y)

            {

                f[j][q[i].x] = f[j][q[i].y] = inv2 * (f[j][q[i].x] + f[j][q[i].y]) % p;

                f[q[i].y][j] = f[q[i].x][j] = inv2 * (f[q[i].y][j] + f[q[i].x][j]) % p;

            }

        }

    }

    ll ans = 0;

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

    {

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

        {

            ans += f[i][j];

        }

    }

    printf("%lld", ans % p * ksm(2, m) % p);

    return 0;

}

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

using namespace std;

#define N 3005

#define mod 1000000007

#define inv 500000004

int n,dp[N][N],v[N],q,a,b;

int main()

{

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

	for(int i=1;i<=n;i++)scanf("%d",&v[i]);

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

	for(int j=1;j<=n;j++)dp[i][j]=(v[i]<v[j]);

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

	{

		scanf("%d%d",&a,&b);

		int tp=dp[a][b]+dp[b][a];

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

		{

			dp[j][a]=dp[j][b]=1ll*(dp[j][a]+dp[j][b])*inv%mod;

			dp[a][j]=dp[b][j]=1ll*(dp[a][j]+dp[b][j])*inv%mod;

		}

		dp[a][b]=dp[b][a]=1ll*tp*inv%mod;

	}

	int as=0;

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

	for(int j=1;j<i;j++)as=(as+dp[i][j])%mod;

	for(int i=1;i<=q;i++)as=as*2%mod;

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

}

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

using namespace std;

const int maxn=3e3+10;

const int mod=1e9+7,inv2=(mod+1)/2;

int a[maxn],dp[maxn][maxn];

int n,m,all=1;

int main()

{

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

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

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

	for(int j=1;j<=n;j++)dp[i][j]=a[i]<a[j];

	while(m--)

	{

		int x,y;

		all=all*1LL*2%mod;

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

		dp[x][y]=dp[y][x]=inv2*1LL*(dp[x][y]+dp[y][x])%mod;

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

		{

			if(i==x||i==y)continue;

			dp[i][x]=dp[i][y]=inv2*1LL*(dp[i][x]+dp[i][y])%mod;

			dp[x][i]=dp[y][i]=inv2*1LL*(dp[x][i]+dp[y][i])%mod;

		}

	}

	int ans=0;

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

	for(int j=1;j<i;j++)ans+=dp[i][j]*1LL*all%mod,ans%=mod;

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

}

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

using namespace std;

#define N 3005

#define mod 1000000007

#define inv 500000004

int n,dp[N][N],v[N],q,a,b;

int main()

{

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

	for(int i=1;i<=n;i++)scanf("%d",&v[i]);

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

	for(int j=1;j<=n;j++)dp[i][j]=(v[i]<v[j]);

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

	{

		scanf("%d%d",&a,&b);

		int tp=dp[a][b]+dp[b][a];

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

		{

			dp[j][a]=dp[j][b]=1ll*(dp[j][a]+dp[j][b])*inv%mod;

			dp[a][j]=dp[b][j]=1ll*(dp[a][j]+dp[b][j])*inv%mod;

		}

		dp[a][b]=dp[b][a]=1ll*tp*inv%mod;

	}

	int as=0;

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

	for(int j=1;j<i;j++)as=(as+dp[i][j])%mod;

	for(int i=1;i<=q;i++)as=as*2%mod;

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

}

//111222333
// Slower C++ solution:
#include<cstdio>

#include<iostream>

using namespace std;

const int mod=1e9+7;

const int r=(mod+1)>>1;

inline int add(int x)

{

	return x>=mod?x-mod:x;

}

int n,Q;

int a[3050];

int f[3050][3050]; 

int t[3050][3050];

int main()

{

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

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

	{

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

	}

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

	{

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

		{

			if(a[i]>a[j]) f[i][j]=1;

		}

	} 

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

	{

		int x,y; scanf("%d%d",&x,&y);

		for(int j=1;j<=n;++j) if(j!=x)

		{

			t[j][x]=1ll*(f[j][x]+f[j][y])*r%mod;

			t[x][j]=1ll*(f[x][j]+f[y][j])*r%mod;

		}

		for(int j=1;j<=n;++j) if(j!=y)

		{

			t[j][y]=1ll*(f[j][y]+f[j][x])*r%mod;

			t[y][j]=1ll*(f[y][j]+f[x][j])*r%mod;

		}

		t[x][y]=1ll*(f[x][y]+f[y][x])*r%mod;

		t[y][x]=1ll*(f[y][x]+f[x][y])*r%mod;

		for(int j=1;j<=n;++j) if(j!=x)

		{

			f[j][x]=t[j][x];

			f[x][j]=t[x][j];

		}

		for(int j=1;j<=n;++j) if(j!=y)

		{

			f[j][y]=t[j][y];

			f[y][j]=t[y][j];

		}

		f[x][y]=t[x][y];

		f[y][x]=t[y][x];

	}

	int an=0;

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

	{

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

		{

			an=add(an+f[i][j]);

		}

	}

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

	{

		an=add(an<<1);

	}

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

	return 0;

}

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

using namespace std;

#define N 3005

#define mod 1000000007

#define inv 500000004

int n,dp[N][N],v[N],q,a,b;

int main()

{

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

	for(int i=1;i<=n;i++)scanf("%d",&v[i]);

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

	for(int j=1;j<=n;j++)dp[i][j]=(v[i]<v[j]);

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

	{

		scanf("%d%d",&a,&b);

		int tp=dp[a][b]+dp[b][a];

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

		{

			dp[j][a]=dp[j][b]=1ll*(dp[j][a]+dp[j][b])*inv%mod;

			dp[a][j]=dp[b][j]=1ll*(dp[a][j]+dp[b][j])*inv%mod;

		}

		dp[a][b]=dp[b][a]=1ll*tp*inv%mod;

	}

	int as=0;

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

	for(int j=1;j<i;j++)as=(as+dp[i][j])%mod;

	for(int i=1;i<=q;i++)as=as*2%mod;

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

}

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

const int MAX=5100;

const int modn=1e9+7;

typedef long long ll ;

#define endl '\n'

#define cwk     freopen("D:\\workplace\\CLion\\in.in","r",stdin),freopen("D:\\workplace\\CLion\\out.out","w",stdout)

using namespace std;

ll n,k;

ll p[MAX],c[MAX];

ll maxnn[MAX];

vector<ll>v[MAX];

int main() {

    cin>>n>>k;

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

        cin>>p[i];

    }

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

        cin>>c[i];

    }

    ll maxn=-INT_MAX;

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

        maxnn[i]=-INT_MAX;

        ll ans = 0;

        for (int j = p[i]; j != i; j = p[j]) {

            ans += c[j];

            v[i].push_back(ans);

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

        }

        v[i].push_back(ans + c[i]);

        maxnn[i]=max(maxnn[i],ans+c[i]);

        ll all=v[i][v[i].size()-1];

        int cnt=k;

        ll now=-INT_MAX;

        if(all<=0){

            now=maxnn[i];

        }else{

            for(int j=0;j<cnt%v[i].size();j++){

                now=max(now,v[i][j]);

            }

            if(k>=v[i].size()) {

                if (all - maxnn[i] + now < 0) {

                    now = maxnn[i] + (k / v[i].size() - 1) * all;

                } else {

                    now += k / v[i].size() * all;

                }

            }

        }

        maxn=max(maxn,now);

    }

    cout<<maxn;

    return 0;

}


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

const int MAX=5100;

typedef long long ll ;

using namespace std;

int n,k;

ll p[MAX],c[MAX];

vector<ll>v;

int main() {

    cin>>n>>k;

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

        cin>>p[i];

    }

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

        cin>>c[i];

    }

    ll all_max=-INT_MAX;

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

        v=vector<ll>();

        ll now_max=-INT_MAX;

        ll ans=0;

        ll now=-INT_MAX;

        for(int j=p[i];j!=i;j=p[j]){

            ans+=c[j];

            v.push_back(ans);

            now_max=max(now_max,ans);

        }

        ans+=c[i];

        now_max=max(now_max,ans);

        v.push_back(ans);

        int cnt=v.size();

        ll all=v[cnt-1];

        if(k<=cnt){

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

                now=max(now,v[j]);

            }

        }else{

            if(all<=0)

                now=now_max;

            else {

                int count=k;

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

                    now = max(now, v[j]);

                }

                if (all - now_max + now < 0) {

                    now = now_max;

                    count-=cnt;

                }

                now += count / cnt * all;

            }

        }

        all_max=max(all_max,now);

    }

    cout<<all_max;

    return 0;

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

const int MAX=5100;

const int modn=1e9+7;

typedef long long ll ;

#define endl '\n'

#define cwk     freopen("D:\\workplace\\CLion\\in.in","r",stdin),freopen("D:\\workplace\\CLion\\out.out","w",stdout)

using namespace std;

ll n,k,now_maxn,all_maxn;

ll p[MAX],c[MAX];

vector<ll>v[MAX];

int main() {

    cin>>n>>k;

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

        cin>>p[i];

    }

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

        cin>>c[i];

    }

    all_maxn=-INT_MAX;

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

        now_maxn=-INT_MAX;

        ll ans = 0;

        for (int j = p[i]; j != i; j = p[j]) {

            ans += c[j];

            v[i].push_back(ans);

            now_maxn=max(now_maxn,ans);

        }

        ans+=c[i];

        v[i].push_back(ans);

        now_maxn=max(now_maxn,ans);

        /*for(int j=0;j<v[i].size();j++)

            cout<<v[i][j]<<" ";

        cout<<"\n";*/

        ll all=v[i][v[i].size()-1];

        ll now=-INT_MAX;

        if(all<=0){

            now=now_maxn;

        }else{

            for(int j=0;j<k%v[i].size();j++){

                now=max(now,v[i][j]);

            }

            if(k>=v[i].size()) {

                if (all - now_maxn + now < 0) {

                    now = now_maxn + (k / v[i].size() - 1) * all;

                } else {

                    now += k / v[i].size() * all;

                }

            }

        }

        all_maxn=max(all_maxn,now);

    }

    cout<<all_maxn;

    return 0;

}


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

const int MAX=5100;

typedef long long ll ;

using namespace std;

int n,k;

ll p[MAX],c[MAX];

vector<ll>v;

int main() {

    cin>>n>>k;

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

        cin>>p[i];

    }

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

        cin>>c[i];

    }

    ll all_max=-INT_MAX;

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

        v=vector<ll>();

        ll now_max=-INT_MAX;

        ll ans=0;

        ll now=-INT_MAX;

        for(int j=p[i];j!=i;j=p[j]){

            ans+=c[j];

            v.push_back(ans);

            now_max=max(now_max,ans);

        }

        ans+=c[i];

        now_max=max(now_max,ans);

        v.push_back(ans);

        int cnt=v.size();

        ll all=v[cnt-1];

        if(k<=cnt){

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

                now=max(now,v[j]);

            }

        }else{

            if(all<=0)

                now=now_max;

            else {

                int count=k;

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

                    now = max(now, v[j]);

                }

                if (all - now_max + now < 0) {

                    now = now_max;

                    count-=cnt;

                }

                now += count / cnt * all;

            }

        }

        all_max=max(all_max,now);

    }

    cout<<all_max;

    return 0;

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

using namespace std;

const int64_t INF = (1LL << 60);

int64_t N, K;

vector<int64_t> scores[5005];

vector<int64_t> P(5005), C(5005);

int64_t tot[5005];

vector<int64_t> maxs(5005, -INF);



bool visited[5005];

void dfs(int64_t v, int64_t score, int64_t start)

{

  if (visited[v])

  {

    scores[start].push_back(score);

    tot[start] = score;

    return;

  }

  visited[v] = true;

  scores[start].push_back(score);

  dfs(P.at(v), score + C.at(P.at(v)), start);

}



int main()

{

  cin >> N >> K;

  for (int64_t i = 0; i < N; i++)

  {

    cin >> P.at(i);

    P.at(i)--;

  }

  for (int64_t i = 0; i < N; i++)

  {

    cin >> C.at(i);

  }

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

  {

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

    {

      visited[j] = false;

    }

    dfs(i, 0, i);

  }

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

  {

    int64_t cyc = scores[i].size() - 1;

    int64_t cycles = K / cyc, r = K % cyc;

    if (tot[i] < 0 || cycles == 0)

    {

      int64_t ma = -INF;

      for (int j = 1; j <= min(K, cyc); j++)

      {

        ma = max(ma, scores[i].at(j));

      }

      maxs[i] = ma;

    }

    else

    {

      if (r == 0)

      {

        int64_t ma = -INF;

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

        {

          ma = max(ma, scores[i].at(j));

        }

        ma += (cycles - 1) * tot[i];

        maxs[i] = ma;

      }

      else

      {

        int64_t ma = 0;

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

        {

          ma = max(ma, scores[i].at(j));

        }

        ma += cycles * tot[i];

        maxs[i] = ma;

      }

    }

  }

  int64_t ans = -INF;

  for (int64_t i = 0; i < N; i++)

  {

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

  }

  cout << ans << endl;

}

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

using namespace std;

int64_t N, K, p, c;

vector<int64_t> to(5005), C(5005);



int64_t solve(int start)

{

  vector<bool> visited(N, false);

  int64_t k = K, score = 0, moves = 0, ret = -(1LL << 62), next = to[start];

  while (!visited[next])

  {

    visited[next] = true;

    moves++;

    score += C.at(next);

    ret = max(ret, score);

    if (moves == K)

    {

      return ret;

    }

    next = to[next];

  }

  if (score <= 0)

  {

    return ret;

  }

  if (k % moves == 0)

  {

    return score * (k / moves - 1) + ret;

  }

  ret = score = score * (k / moves), k %= moves;



  while (k > 0)

  {

    k--;

    score += C.at(next);

    ret = max(ret, score);

    next = to[next];

  }

  return ret;

}



int main()

{

  cin >> N >> K;

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

  {

    cin >> to[i];

    to[i]--;

  }

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

  {

    cin >> C.at(i);

  }

  int64_t ans = -(1LL << 62);

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

  {

    ans = max(ans, solve(i));

  }

  cout << ans << endl;

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;



const int Maxn=2*1e5;



char s[Maxn+5],t[Maxn+5];

int c[256+5];



int main() {

	#ifdef LOACL

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

	freopen("out.txt","w",stdout);

	#endif

	scanf("%s %s",s,t);

	int len=strlen(s);

	memset(c,-1,sizeof c);

	set<char> cnt;

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

		cnt.insert(s[i]);

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

		if(c[t[i]]!=-1&&c[t[i]]!=s[i]) {

			if(t[i]==s[i]&&cnt.size()<26)

				continue;

			puts("No");

			return 0;

		}

		c[t[i]]=s[i];

	}

	memset(c,-1,sizeof c);

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

		if(c[s[i]]!=-1&&c[s[i]]!=t[i]) {

			if(t[i]==s[i]&&cnt.size()<26)

				continue;

			puts("No");

			return 0;

		}

		c[s[i]]=t[i];

	}

	puts("Yes");

	return 0;

}

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

#include<cstring>

using namespace std;

#define L 200005



char s[L],t[L];

int len,last[30];

int lasts[L],lastt[L];

bool flag=true;



int main() {

	scanf("%s %s",s,t);

	len=strlen(s);

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

		int j=s[i]-'a';

		lasts[i]=last[j];

		last[j]=i;

	}

	memset(last,0,sizeof(last));

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

		int j=t[i]-'a';

		lastt[i]=last[j];

		last[j]=i;

	}

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

		if(lasts[i]!=lastt[i]) {

			printf("No\n");

			return 0;

		}

	printf("Yes\n");

	return 0;

}