#include <bits/stdc++.h> using namespace std; /* ------------------------Input Checker---------------------------------- */ long long readInt(long long l,long long r,char endd){ long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true){ char g=getchar(); if(g=='-'){ assert(fi==-1); is_neg=true; continue; } if('0'<=g && g<='9'){ x*=10; x+=g-'0'; if(cnt==0){ fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd){ if(is_neg){ x= -x; } if(!(l <= x && x <= r)) { cerr << l << ' ' << r << ' ' << x << '\n'; assert(1 == 0); } return x; } else { assert(false); } } } string readString(int l,int r,char endd){ string ret=""; int cnt=0; while(true){ char g=getchar(); assert(g!=-1); if(g==endd){ break; } cnt++; ret+=g; } assert(l<=cnt && cnt<=r); return ret; } long long readIntSp(long long l,long long r){ return readInt(l,r,' '); } long long readIntLn(long long l,long long r){ return readInt(l,r,'\n'); } string readStringLn(int l,int r){ return readString(l,r,'\n'); } string readStringSp(int l,int r){ return readString(l,r,' '); } /* ------------------------Main code starts here---------------------------------- */ const int MAX_T = 1e5; const int MAX_N = 1e5; const int MAX_SUM_LEN = 1e5; #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define ff first #define ss second #define mp make_pair #define ll long long #define rep(i,n) for(int i=0;i<n;i++) #define rev(i,n) for(int i=n;i>=0;i--) #define rep_a(i,a,n) for(int i=a;i<n;i++) #define pb push_back int sum_n = 0, sum_m = 0, sum = 0; int max_n = 0, max_m = 0; int yess = 0; int nos = 0; int total_ops = 0; ll mod = 1000000007; ll INF = 1e18; using ii = pair<ll,ll>; void maxi(ii &a, ii b){ if(b.ss<=0) return; if(b.ff>a.ff){ a = b; a.ss%=mod; } else if(a.ff==b.ff && b.ss>0){ a.ss+=b.ss; a.ss%=mod; if(a.ss<0) a.ss+=mod; } } void solve() { int n = readIntSp(1,2e3); int k = readIntSp(1,2e3); ll m = readIntSp(1,1e9); mod = readIntLn(2,1e9); ll a[n+1], p[n+k+1], c[n+k+1]; rep_a(i,1,n+1){ if(i<n) a[i] = readIntSp(1,m); else a[i] = readIntLn(1,m); } rep_a(i,1,n+k+1){ if(i<n+k) p[i] = readIntSp(1,m); else p[i] = readIntLn(1,m); } rep_a(i,1,n+k+1){ if(i<n+k) c[i] = readIntSp(-1e9,1e9); else c[i] = readIntLn(-1e9,1e9); } vector<vector<ii> > dp(n+k+1, vector<ii>(n+1, mp(-INF, 0))); dp[0][0] = mp(0ll,1ll); rep_a(i,1,n+k+1){ rep(j,n+1){ if(j>i) break; if(j==0){ if(!n){ maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-1))); } else{ if(p[i]==a[j+1]) maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-1))); else{ maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); } } } else if(j==n){ maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); if(a[j]==p[i]){ maxi(dp[i][j], mp(dp[i-1][j-1].ff+c[i], dp[i-1][j-1].ss)); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-1))); } else{ maxi(dp[i][j], dp[i-1][j-1]); maxi(dp[i][j], dp[i-1][j]); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); } } else{ // if(p[i]==a[j]){ // maxi(dp[i][j], mp(dp[i-1][j-1].ff+c[i], dp[i-1][j-1].ss)); // if(a[j]==a[j+1]) maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-1))); // else{ // maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); // maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); // } // } // else if(a[j]==a[j+1]){ // maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); // maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); // maxi(dp[i][j], dp[i-1][j-1]); // } // else if(p[i]==a[j+1]){ // maxi(dp[i][j], dp[i-1][j-1]); // maxi(dp[i][j], dp[i-1][j]); // maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); // } // else{ // maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); // maxi(dp[i][j], dp[i-1][j-1]); // maxi(dp[i][j], dp[i-1][j]); // maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-3))); // } if(p[i]==a[j] && a[j]==a[j+1]){ maxi(dp[i][j], mp(dp[i-1][j-1].ff+c[i], dp[i-1][j-1].ss)); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-1))); } else if(a[j]!=a[j+1] && a[j]!=p[i] && a[j+1]!=p[i]){ maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); maxi(dp[i][j], dp[i-1][j-1]); maxi(dp[i][j], dp[i-1][j]); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-3))); } else if(a[j]==a[j+1]){ maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); maxi(dp[i][j], dp[i-1][j-1]); } else if(a[j]==p[i]){ maxi(dp[i][j], mp(dp[i-1][j-1].ff+c[i], dp[i-1][j-1].ss)); maxi(dp[i][j], mp(dp[i-1][j].ff+c[i], dp[i-1][j].ss)); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); } else if(a[j+1]==p[i]){ maxi(dp[i][j], dp[i-1][j-1]); maxi(dp[i][j], dp[i-1][j]); maxi(dp[i][j], mp(dp[i-1][j].ff, dp[i-1][j].ss*(m-2))); } } } } cout<<dp[n+k][n].ff<<" "<<dp[n+k][n].ss<<'\n'; } signed main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r" , stdin); freopen("output.txt", "w" , stdout); #endif fast; int t = 1; //t = readIntLn(1,1e5); for(int i=1;i<=t;i++) { solve(); } assert(getchar() == -1); //assert(sum_n<=2e5); cerr<<"SUCCESS\n"; cerr<<"Tests : " << t << '\n'; cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n'; // cerr<<"Maximum length : " << max_n <<'\n'; // // cerr<<"Total operations : " << total_ops << '\n'; // cerr<<"Answered yes : " << yess << '\n'; // cerr<<"Answered no : " << nos << '\n'; cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"; }