#include<bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int n,s; int p[5010],w[5010],a[5010]; vector<int>gr[5010]; vector<int>R; bool r[5010],vis[5010]; stack<int>S; inline void dfs(int u){ vis[u]=1; S.push(u); for(int v:gr[u]){ if(vis[v]){ while(!S.empty()){ int x=S.top(); R.push_back(x); r[x]=1; S.pop(); if(x==v)break; } } else dfs(v); } if(!S.empty()&&S.top()==u)S.pop(); } int f[5010][5010]; int pf[5010][5010]; inline void calc(int u){ for(int i=0;i<=n+2;i++) f[u][i]=(i%2)*w[u]-p[u]*i; if(u==s)f[u][0]=-1e18; for(int v:gr[u]) if(!r[v]){ calc(v); for(int i=0;i<=n+2;i++) f[u][i]+=pf[v][i]; } pf[u][0]=f[u][0]; for(int i=1;i<=n;i++) pf[u][i]=max(pf[u][i-1],f[u][i]); } int g[5010][5010][3]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("color2.in","r",stdin); // freopen("color.out","w",stdout); int t; cin>>t; while(t--){ cin>>n>>s; R.clear(); for(int i=1;i<=n;i++)gr[i].clear(),vis[i]=0,r[i]=0; for(int i=1;i<=n;i++)cin>>w[i]; for(int i=1;i<=n;i++)cin>>p[i]; for(int i=1;i<=n;i++)cin>>a[i],gr[a[i]].push_back(i); dfs(s); // return 0; if(R.empty())calc(s),cout<<max(f[s][1],f[s][2])<<endl; else if(R.size()==2)calc(s),calc(R[0]), cout<<max({f[s][1]+f[R[0]][1],f[s][1]+f[R[0]][0],f[s][2]+f[R[0]][0]})<<endl; else{ for(int i=0;i<=n+2;i++) memset(g[i],-0x3f,sizeof(g[i])); for(int i=0;i<=n;i++) g[0][i][0]=0; int c=0; for(int x:R){ calc(x); // cout<<x<<endl; // for(int i=0;i<=n+2;i++) // cout<<f[x][i]<<" "; // cout<<endl; c++; for(int i=0;i<=n;i++) for(int j=0;j<=2;j++) for(int k=j;k<=2;k++) g[c][i][k]=max(g[c][i][k],g[c-1][i][j]+f[x][i+k]); } int res=-1e18; for(int i=0;i<=n;i++) for(int j=0;j<=2;j++) res=max(res,g[c][i][j]); cout<<res+p[1]<<endl; } } cout.flush(); return 0; }