#include #include #include using namespace std; const long long INF = (1LL << 50); template class Matrix { public: explicit Matrix(int N) : m(N, vector(N, 0)) {} static Matrix ident(int N) { Matrix res(N); for(int i=0;i& operator [](int n) { return m[n]; } const vector& operator [](int n) const { return m[n]; } int size() const { return m.size(); } public: vector> m; }; template Matrix mul(const Matrix& a, const Matrix& b){ const int N = a.size(); Matrix res(N); for(int i=0;i Matrix pow(const Matrix& a, int p){ const int N = a.size(); if(p == 0) return Matrix::ident(N); if(p == 1) return a; auto res = pow(a, p/2); res = mul(res, res); if(p%2) res = mul(res, a); return res; } bool solve(){ vector C(26); for(auto& c : C){ if(!(cin >> c)) return false; } vector K(26); for(auto& k : K) cin >> k; int N; cin >> N; vector> v(26, Matrix::ident(26)); for(int i=0;i> S >> A >> B >> E; for(auto& s : S){ if(v[s-'A'][A-1][B-1] < E){ v[s-'A'][A-1][B-1] = v[s-'A'][B-1][A-1] = E; } } } vector res(26, 0); for(int i=0;i<26;i++){ auto m = pow(v[i], K[i]); for(int j=0;j<26;j++){ if(res[j] < -INF) continue; if(m[C[i]-1][j] == -INF){ res[j] = -INF-1; } else { res[j] += m[C[i]-1][j]; } } } long long best = -INF; for(auto& t : res) best = max(t, best); if(best == -INF){ cout << "Impossible" << endl; } else { cout << best << endl; } return true; } int main(){ while(solve()); }