#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; templatebool chmax(T &a, const T &b) {if(abool chmin(T &a, const T &b) {if(b struct Matrix{ vector> val; Matrix(){} Matrix(int n,int m,T x=e_ADD()):val(n,vector(m,x)){} Matrix(vector> a):val(a){} size_t size() const {return val.size();} inline vector& operator [] (int i) {return val[i];} using MULT = function; using ADD = function; static MULT &get_mult(){ static MULT mult = nullptr; return mult; } static T &e_MULT(){ static T em = 1; return em; } static void set_mult(MULT f,T e) { get_mult() = f; e_MULT() = e; } static T &e_ADD(){ static T ea = 0; return ea; } static ADD &get_add(){ static ADD add = nullptr; return add; } static void set_add(ADD f,T e) { get_add() = f; e_ADD() = e; } Matrix &operator=(const vector> &A) { int n=A.size(),m=A[0].size(); val=A; return *this; } Matrix &operator+=(const Matrix &A) { assert(get_add() != nullptr); for (int i=0;i &operator+=(const vector> &A) { return *this += Matrix(A); } Matrix &operator*=(const Matrix &A) { assert(get_add() != nullptr); assert(get_mult() != nullptr); Matrix R(val.size(),A.val[0].size()); for (int i = 0; i < val.size(); ++i) for (int j = 0; j < A.val[0].size(); ++j) for (int k = 0; k < A.size(); ++k) R[i][j] = get_add()(R[i][j],get_mult()(val[i][k],A.val[k][j])); for (int i=0;i &operator*=(const vector> &A) { return *this *= Matrix(A); } Matrix operator+(const Matrix &p) const { return Matrix(*this) += p; } Matrix operator-(const Matrix &p) const { return Matrix(*this) -= p; } Matrix operator*(const Matrix &p) const { return Matrix(*this) *= p; } bool operator==(const Matrix &p) const { return val == p.val; } bool operator!=(const Matrix &p) const { return val != p.val; } Matrix pow(long long n) { Matrix A=*this; Matrix R(A.size(), A.size(),e_ADD()); for (int i = 0; i < A.size(); ++i) R[i][i] = e_MULT(); while (n > 0) { if (n & 1) R = R * A; A = A * A; n >>= 1; } return R; } }; using Mat = Matrix; int C[26],K[26],n,m=16,l=26; vector S[200010];int A[200010],B[200010];ll E[200010]; Mat mat[26]; ll ans[16];bool ng[16]; void solve(){ auto add=[](ll a,ll b){return max(a,b);}; auto mult=[](ll a,ll b){return a+b;}; Mat::set_add(add,-INF); Mat::set_mult(mult,0); rep(i,26) { cin >> C[i];C[i]--; } rep(i,26) cin >> K[i]; cin >> n; rep(i,n){ string s; cin >> s >> A[i] >> B[i] >> E[i]; A[i]--;B[i]--; S[i].resize(l,0); rep(j,s.length()){ S[i][s[j]-'A']=1; } } rep(i,l){ mat[i]=Mat(m,m); rep(j,m){ mat[i][j][j]=0; } rep(j,n){ if(S[j][i]) { mat[i][A[j]][B[j]]=E[j]; mat[i][B[j]][A[j]]=E[j]; } } mat[i]=mat[i].pow(K[i]); rep(j,m){ //cout << mat[i][C[i]][j] << " "; if(mat[i][C[i]][j]==-INF) ng[j]=true; ans[j]+=mat[i][C[i]][j]; } //cout << "" << endl; // rep(p,m){ // rep(q,m){ // cout << mat[i][p][q] << " "; // } // cout << "" << endl; // } } ll A=-INF; rep(i,m){ //cout << i << " " << ans[i] << endl; if(!ng[i]) chmax(A,ans[i]); } if(A==-INF) cout << "Impossible" << endl; else cout << A << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }