template originalSource() =
 # {.checks: off.}
 include cplib/tmpl/citrus
 
 var t = 26
 var m = 16
 var c = input(int, t)
 var k = input(int, t)
 var n = input(int)
 var sabe = newSeqWith(n, input(string, int, int, int))
 
 var ans = newSeqWith(m, 0)
 proc matmul(a, b: seq[seq[int]]): seq[seq[int]] =
     var ans = newSeqWith(m, newSeqWith(m, -INFL))
     for k in 0..<m:
         for i in 0..<m:
             for j in 0..<m:
                 if a[i][k] == -INFL or b[k][j] == -INFL: continue
                 ans[i][j].max = a[i][k] + b[k][j]
     return ans
 for x in 0..<t:
     var g = newSeqWith(m, newSeqWith(m, -INFL))
     for i in 0..<m:
         g[i][i] = 0
     for (s, a, b, e) in sabe:
         if char(int('A') + x) notin s: continue
         g[a-1][b-1].max = e
         g[b-1][a-1].max = e
     var a = newSeqWith(m, newSeqWith(m, -INFL))
     a[c[x]-1][c[x]-1] = 0
     var y = k[x]
     while y > 0:
         if (y and 1) == 1:
             a = matmul(a, g)
         g = matmul(g, g)
         y >>= 1
     # for row in a: debug(row)
     for i in 0..<m:
         if a[c[x]-1][i] == -INFL:
             ans[i] = -INFL
         if ans[i] == -INFL: continue
         ans[i] += a[c[x]-1][i]
 
 debug(ans)
 var ansi = -INFL
 for i in 0..<m:
     if ans[i] != -INFL: ansi.max = ans[i]
 if ansi == -INFL: print("Impossible")
 else: print(ansi)
 



# https://github.com/kemuniku/cplib
import macros;macro cplibRestore(s:static[string]):untyped = parseStmt(s)
cplibRestore("import base64\x0Amacro cplibUnpackSource(): untyped =\x0A    # \xE3\x82\xB3\xE3\x83\xB3\xE3\x83\x91\xE3\x82\xA4\xE3\x83\xAB\xE6\x99\x82\xE3\x81\xAB\xE5\xB1\x95\xE9\x96\x8B\xE6\xB8\x88\xE3\x81\xBF\xE3\x82\xB3\xE3\x83\xBC\xE3\x83\x89\xE3\x82\x92\xE5\xBE\xA9\xE5\x85\x83\xE3\x81\x99\xE3\x82\x8B\xE3\x80\x82\x0A    let z = decode(\"ACMgey5jaGVjAGtzOiBvZmYuAH0KIyBzb3VyAGNlOiBodHRwAHM6Ly9naXRoAHViLmNvbS9rAGVtdW5pa3UvAGNwbGliL3RyAGVlL21haW4vCHNyYwAUBW1wbC8AY2l0cnVzLm4AaW0Kd2hlbiAAbm90IGRlY2wAYXJlZCBDUEwASUJfVE1QTF8AQ0lUUlVTOgqCIAABAGNvbnN0AB0PICogPSAxACECey4Ad2FybmluZ1sAVW51c2VkSW1gcG9ydF0AuQUAIwNoQGludFtYRABsBELAdXROb3RVAC0AACcKImkAOgIgb3MADglhbChnb3IA6wBtABUJc2UgcXV0aWwAKQp0YQhibGUAEgptYWNykQBNC3N0ZAEZAHRoAEwLGnQAJAxyAFwOABQAZm9yQwA6AAAVCnVnYXIAJgxlNGFtADkKZACpAACVC2JpCHRvcAASCmhlYXCJACYAdWUBBQpwdGkBegAxACgKYXNoAEwEAZUDTU8ARElOVDk5ODLgNDQzNTMBkwEADQYAJw70MTAAAQQ3AbsCAA4GACkCAl49xQExAi8AbwJhbnQCYgMAWAEBAmYVVVRJTFNfQ4BPTlNUQU5UAmoEDwJuDQAlDAJyBwApB0lORjOQMio6IAJeADMyANcDMQDaAjI3LgATAgAvDzY0BwAvAwAtAAAGACgzMzAw4QADCTQ5MSkANQIBQAgANgAOTAAvAAA9AgAXAnR5cGUwIGRvdQJwAACVAWZsCG9hdAAbBGxldCAhAgUAZE5leABjAnRlgHJhdG9yKGcCZQAAQ2hhcjogYm8Eb2wANQFhbHNlKQ46AjQBAzsAA+8BbG9zdUByZS59ID0AtgZ3oGhpbGUgApAAZQEiB4EAAQF2YXIgc2kAPQXRABsKdHJ5ABgAaQBiAALsAIhpbi4AjQFMaW4CXAMBAAEFZXhjZXB0IIBFT0ZFcnJvAJUAAHlpZWxkICIiMwAmCgLyACBzASYAAE8ALnONAecAdACFCwABAWlmIADaBgsAHQ4ARAVpAEQBMC4uPIBzLmxlbigpACoTAwABAQCHA3NbaS4uaTpdACYOZQEyAAA8EwCHAHMuAGlzRW1wdHlPiHJXaAF3AHNwYQLPAXEBwgB0aW4DWwQAbxQAHAJwCHJvYwCoAHB1dCoIKHQ6AeMCZGVzY6pbAWMDXQGqBz0B4AYoAioDfQA6FWMBFQAAOAEACAEANgkBzwEp/FswAOADAD0VApwAADwBAqkDAHEHAC5wYXJzZUluvwSIAwA9FQKRAgA/AQAJAgBBEEYAGAGHAEMCBSMCAEQQLCBuOgJnAZhhcmcBjwAAjQN1bgAeAoMCoAgCiAFyZXBTdADhAW8CPggB9gEAOgAB+AFuAbILAC4EJsA9ICYiKHsAJAACoQAAcHJ9KS5uZXfQU2VxVwR2ACAASAcArQIARXhwcigmInsFADsDfQCsAih7dH0pHiIBgAMAwwsHMQAAtwVhdXTSbwC4F3R1ALgTdAC2AQBHAN8DVgsALQMAtwIAgQUAugQsAK8TACEA7wA0AgCnEwFdAAFVACwAaAEAryAAlwJceXAAmREC+gAAGgAuADIBS4BpbmQgIT0gAD8AUEFueXQHcgBnAy4PZYkD8AEoIgClAGVjdABlAMUB8AdnBaYAIiAmAE8CANoB+QCdAHlwALsDANwPBFgBAbcNARgFDnMAHAQA+AQCpQJgZm10gnADPwB0YCooeALXA38EXQEDUgMACgADJAIACAAFHQEDawt0wHVybiAkeABLFgLjA88AOwAACQIGBQAACwU2NABJEAJHAIB4Oi4xNmZ9AbYD8QBSDVtUXQBVAQhfAAAKAABLARZEB8ABAAwESAeAAFNldA8ADgQINwAACgAAZBB4LnRvAQEUAC5qb2luKCKCIAEHFFtULCBOAG0C4GFycmF5AA8DAE44AEsCukgISgBRCEoBAJoLAvgKcQBcALcBTwMAAQEGYgNxBZkBAjwBMAOuDRBzdWx0AvcDe3Eu4HBvcCgpAToEAoEIAD4IpwAyCACsAACrGUNvAugAVAmzAY8ArBQASgQArQAEtABpcnMBCAQgbWFwSXQEDwFpdBEFRAB9OiAACQExXX2EIikBIx1LLCBWAHsCTwB2AwAPAgB5VgB1AiooAAwAcAkFVQB1cABxAGY6IEYlAW0ALAI6AHBjAHgFLCAIZW5kAA4IZmx1c/JoCCUDXSwFRAEEIQgAJAUA1Qf8XSkEJgwHawYHaQEANQEHbQwAkAHQLmYudwtRAGUAzAEF3wMbAMUBAdUNaQHRAQBGBiAtINwxOgA+CwANAgDLASkHmQMAHhD/ANsBAFkHAFUAACMDAOMDAC8EAA4CARgBzwdOCQE+BAD/IQAsAygoAV4ACPEAPG91BVUAAWADAZAAAV0FIlx+bgAMAAB4BAl5AwFcAwBzAwnmA0wAT0NBTF9ERUIQVUd7LgGAAWRlZh8JOAAJkAEANAMFxggI9ABTeW2AYm9sTmFtZQJTAYcFRwIDvgkDtwJ0ckxpB2cJ4GRlYnVnANcNBe8EBfoTDwtAAgCaCAOfEgXzAGV3TmkAbU5vZGUobm4Aa1N0bXRMaXMnAQoAAOQHAAEFdGUOCABhdJplAX8CKAG2AACyBiIiAIIJ/iABUQQGMAABUQYBUAYCxAABTQQIzAJ9CjUOaQB6AgKLAQDrAgo2EQf6AWt9BrEBPQC+AACzAQErAQndEwDmAy6AYWRkKHF1bwC7ADxkbwI+AQH2AQDFAgHMACJc1QCdAWAAVQBgAA0DKQCVCwABAXsKPhcAYR0iAPwAAGUAAfULAG0CKf8AaBAAsyQAQAQBHBEDewIBOgEFWAIDegLvAQQhAAMAAPcVAUQjbgBACQEvDwaRBAEAQQhkaXNjYXJkRQVwCSUHlgNTb20KpgFlfGdlAj8ADJEAABAICtYFBXAQICBtb2QgeQQxCXkgYD4gMCBhAigAACYEPPkGZQgrPQAtDQAeAAAtCQA8AAAtD4kAqAMvLwCpOmRpdgCpHO4qABMCAGIAABAELQ69CQCtEQAxAbY8ADERALEDXgCwJgCfAHgDhQDdAO4JJgA9KQCUAQA9CXwAPSkAeQwkPj4APSlzaAA+Czw85QA+K2wAPgolPQA+Awj1AQBCG6h2b2kE8wF4AAQCJQIoDKkARjMvLwBHCl4ARjNeAcYLbQBFMyYBzgsARTN8AdcMAEYzPiY+AeAMAEczPDwARwpbXV8ARgEOsgICDAAALQARYwQoAswDKOIxAhsCbikpCqQCADkKAIAIvw2QAg2YBRFcAAyLAgP+CAWZAToAgQSXAuYAAFYAAIcAbgUxDCAoACcA+HhbbhTXAAAqAwOKAQArBQjhCexvdwgIAABwB20SYAUEdQ4AmwCtBYYMdhMICgABAWEAEgBhABIKtm4IFQEL5QxuBRACCegNbgLxABYyC70GAFwBKAAHASogYW4pBY8CE8gDADEKPgaSAQB0ASj2YQAoFQAlAD4ApgkGPAQAWgAAEwIDFG89FcMBL2lzcXJ0ARRqHk1BVEhfSVP4UVJUFGUTACAHFGALEVwDAGMBfw+uBQGbDgABAQI6AQHqAQFtBwAWBXnhAoIDKyAxKQTZAgGzCwGTA78F8gMHtA4AUQEGXgcAAQUAUQZuBn8CHngAVxEONQUAFQICbwdjaG28YXgNegUAnQEObgADYwBUAywF/HsuB8sEDRoBCvICAsgCAJ4AACYAGwB0AACPADsAXAUJ8wE7ICnnAA8FC08DAGsKaW4AazAEGgAAay1+YADVAAPBAABsEAQqBAAgAAQYAXm5ADQKaW4ANBsNywAANAxhAgMAjwAtABCkAQrZAAAkACcwJwZ4BisJQwEBiwAtAAkCYQA2CFll8HMqKGIEjQYLKgIEyAYJewMrAPkAACEAIgAqACIEPwQiTrJvDkYJTm8AQxcANgAoAvABAmIAdAlFU191cHCkZXIAeiVFUwB6B08Aego+TwBJHQCAAAAjAwCGCQNaA0RYAlkDTQFbKDAsIC0OMQpcAAAJAQAIAi0xLCD+MAAJAQAIAhUDAwA0BAA1BgAbAAA1A78ALAgARQUATg8AEgMAWAYACQExAFkEcQ11A2V4aQHAABiYAAz7AGWebhTjAAzkBAzuCwrVByhgACwGwGA7IHF1aRU2AAW7CfBpbml0EgoHFs4AEhgCEg4DgwIQAgAfCjApCgoKFG8CWQAcADI2AAsCBe0BMQALA2PXADICEzgBFA8DKQAWAmsAFhIF1AHDABYGABMDc2FiZQR9AROFBvwobga8AAAkAg8uBQbPAwAFBADIAFEAOAJhbnMANwttAT8BCuMA4AIFXABtdWwGnQEB+gATCQF/AAQBFgIBES0CABAJBQsEAFEVAA4LLdcZRgEBSAQOJAFrEKoFbQUABxDCCnsAGAgAHAVqABwUAAEBDlQBEMoAWzprAJcAPQBuAxRRAgARAFtqzwAUBxgSGADEAABBAWpdEesABAoBvQBPBSsARQUAMgIEjAQALQAKAJMBfngAkwUOvQQBDQEPTgEBCykA8xFnnQB9AWkCUQEIsQMAKAEocwR/APsBlwAPhwApGZcCAf4AADIHAQEABKIBwQIdASgnQScpALgABJgABwOcAAAqAQD3EGdbYS0x+F1bYgAFAADxBAAcCQAXAQAhAgcAHAoB6wIA3ihhW2NbeN5dAEsBAAgEANAGByIFawAYAAfABOcHEQMIpAoA1AAoeQnFAgdFAAHDAO4xAfgLAIsBAq8HZwmMBwGCAQAZBC8DAwAAGQgAYAAImAYjAVUCcm/udxCpAg7OABGeASgAEAABmhsCaQL/ANcFAaIBAloFAJsLAk0CAIcAABwCAD0KnwAaBAKRFwAiBA6yAABpCQoKAKED/wAeAAP9AwAJABvnAQBhAwCuEQBtBwnfAO8AbQQANQEC4AUAHAIKACYDAEoAACQGxQYjAyIfyAFzc2kHpwAGGQAHE+MFBuYCAC8AKQo=\")\x0A    var s = \"\"\x0A    var i = 0\x0A    while i < z.len:\x0A        let f = ord(z[i])\x0A        inc i\x0A        for b in 0..<8:\x0A            if i >= z.len: break\x0A            if (f and (1 shl b)) == 0:\x0A                s.add(z[i])\x0A                inc i\x0A            else:\x0A                let d = ord(z[i])*256+ord(z[i+1])\x0A                let n = ord(z[i+2])+3\x0A                i += 3\x0A                for j in 0..<n: s.add(s[s.len-d])\x0A    result = parseStmt(s)\x0AcplibUnpackSource()\x0A")