비제네르 암호

비제네르(Vigenère) 암호는 평문에 키를 반복하여 더하는 방식이다. $A = 0$, $B = 1$, $C = 2, \ldots, Z = 25$라고 하자. 각 암호문 글자는 대응하는 평문 글자와 키 글자를 더한 값을 $26$으로 나눈 나머지이며, 키는 필요한 만큼 반복된다. 예를 들어 평문 CPSPCISANABBREVIATION을 키 CPSPC로 암호화하면 EEKEEKHSCCDQJTXKPLXQP가 된다.

길이가 $K$인 키로 암호화된 암호문(공백 없이 대문자로만 이루어진 문자열)이 주어진다. 암호문 글자를 키 글자로 복호화한다는 것은 암호문 글자에서 키 글자를 뺀 값을 $26$으로 나눈 나머지를 구하는 것이다. 또한 평문 언어에서 인접한 두 글자로 이루어진 순서쌍들의 빈도표가 주어진다. 빈도가 클수록 그 쌍이 나타날 가능성이 높다.

길이가 $K$인 키로 암호문을 복호화한 뒤, 만들어진 평문에서 인접한 모든 글자 순서쌍의 빈도를 합한 값을 그 키의 점수로 정의한다. 이러한 빈도 분석은 원문을 놀라울 만큼 잘 복원한다. 길이가 $K$인 모든 키 중에서 얻을 수 있는 점수의 최댓값을 구하여라.

첫째 줄에 두 정수 $K$와 $N$이 주어진다 ($K \le 5000$). $K$는 키의 길이이고, $N$은 빈도가 알려진 글자 쌍의 개수이다.

다음 $N$개의 줄에는 각각 대문자 영어 두 글자(사이에 공백 없이 붙여서)가 주어지고, 한 칸 띄운 뒤 그 순서쌍의 빈도를 나타내는 양의 정수 $F$ ($F \le 10^8$)가 주어진다. 표에 없는 쌍의 빈도는 $0$으로 간주한다.

마지막 줄에는 대문자 영어 글자로만 이루어진, 길이가 $10000$ 미만인 암호문이 주어진다. 전체 텍스트에서 얻을 수 있는 빈도 합의 최댓값은 $10^8$을 넘지 않는다.

길이가 $K$인 모든 키 중에서, 복호화된 평문의 인접한 글자 순서쌍 빈도 합이 최대가 되는 값을 정수 하나로 출력한다.

예제의 암호문을 키 CPSPC로 복호화하면 HELLOIAMENCRYPTEDTEXT가 되며, 이 평문의 인접한 글자 쌍들(예: TE, YP, XT, RY, PT, OI)의 빈도 합은 $9$로, 이 값이 최댓값이다.