#include <bits/stdc++.h> using namespace std; int main() { std::ios_base::sync_with_stdio(false); cin.tie(nullptr); long long n, k, m, mod; cin >> n >> k >> m >> mod; vector<long long> a(n + 1); for (long long i = 1; i <= n; ++i) { cin >> a[i]; } long long lg = n + k; vector<long long> poz(lg + 1); for (int i = 1; i <= lg; ++i) { cin >> poz[i]; } vector<long long> cost(lg + 1); for (long long i = 1; i <= lg; ++i) { cin >> cost[i]; } vector<vector<pair<long long, long long>>> dp(lg + 1, vector<pair<long long, long long>>(n + 1, { -99999999999999 , 0 })); auto update = [&](pair<long long, long long>& a, pair<long long, long long> b) { if (b.first == -99999999999999) { return; } if (b.first > a.first) { a.first = b.first; a.second = b.second; a.second %= mod; } else { if (a.first == b.first) { a.second += b.second; a.second %= mod; } } }; update(dp[0][0], { 0 , 1 }); for (long long i = 1; i <= lg; ++i) { for (long long j = 0; j <= min(n, i); ++j) { if (j == 0) { if (n == 0) { update(dp[i][j], { dp[i - 1][j].first + cost[i] , dp[i - 1][j].second }); if (m - 1 >= 1) { update(dp[i][j], { dp[i - 1][j].first,dp[i - 1][j].second * (m - 1) }); } } else { if (a[j + 1] == poz[i]) { if (m - 1 >= 1) { update(dp[i][j], { dp[i - 1][j].first,dp[i - 1][j].second * (m - 1) }); } } else { update(dp[i][j], { dp[i - 1][j].first + cost[i] , dp[i - 1][j].second }); if (m - 2 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 2) }); } } } continue; } if (j == n) { if (a[j] == poz[i]) { update(dp[i][j], { dp[i - 1][j - 1].first + cost[i] , dp[i - 1][j - 1].second }); update(dp[i][j], { dp[i - 1][j].first + cost[i] , dp[i - 1][j].second }); if (m - 1 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 1) }); } } else { update(dp[i][j], { dp[i - 1][j].first + cost[i] , dp[i - 1][j].second }); update(dp[i][j], dp[i - 1][j]); update(dp[i][j], dp[i - 1][j - 1]); if (m - 2 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 2) }); } } continue; } /* caz 1 : a[j] = a[j+1] = poz[i] caz 2 : a[j] != a[j+1] != poz[i] != a[j] caz 3 : exista o pereche (i,j) in sirul V = [a[j] , a[j+1] , poz[i]] cu proprietatea ca Vi = Vj ( daca ar exista 2 , se ajunge la primu caz , daca ar fi 0 , se ajunge la primul => nu se pot intampla 2 simultan => nu se da overcount ) */ if (a[j] == a[j + 1] && poz[i] == a[j]) { update(dp[i][j], { dp[i - 1][j - 1].first + cost[i] , dp[i - 1][j - 1].second }); if (m - 1 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 1) }); } continue; } if (a[j] != a[j + 1] && a[j] != poz[i] && a[j + 1] != poz[i]) { update(dp[i][j], { dp[i - 1][j].first + cost[i], dp[i - 1][j].second }); update(dp[i][j], dp[i - 1][j - 1]); update(dp[i][j], dp[i - 1][j]); if (m - 3 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 3) }); } continue; } if (a[j] == a[j + 1]) { update(dp[i][j], { dp[i - 1][j].first + cost[i] , dp[i - 1][j].second }); update(dp[i][j], dp[i - 1][j - 1]); if (m - 2 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 2) }); } continue; } if (a[j] == poz[i]) { update(dp[i][j], { dp[i - 1][j - 1].first + cost[i] , dp[i - 1][j - 1].second }); update(dp[i][j], { dp[i - 1][j].first + cost[i] , dp[i - 1][j].second }); if (m - 2 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 2) }); } continue; } if (a[j + 1] == poz[i]) { update(dp[i][j], dp[i - 1][j]); update(dp[i][j], dp[i - 1][j - 1]); if (m - 2 >= 1) { update(dp[i][j], { dp[i - 1][j].first , dp[i - 1][j].second * (m - 2) }); } continue; } } } cout << dp[lg][n].first << ' ' << dp[lg][n].second; }