7720번 - Vigener Cipher 스페셜 저지다국어

Probably everyone have heard about so called Vigener cipher. This cipher adds cyclically repeated key to the original text. The key is added as follows – let us assume that A = 0, B = 1, C = 2 . . .Z = 25. Then we just sum the letter of the original text and the letter of the key modulo 26. For example for the text CPSPCISANABBREVIATION and the key CPSPC we obtain encypted message EEKEEKHSCCDQJTXKPLXQP (see figure).

Your task will be to try to decode the encrypted text, assuming that you know the table of the frequences of all pairs of letters in the language of the encrypted text and the length of the key. Such analyze gives surprisingly good results.

You will get the encrypted text without spaces, which was encrypted by the Vigener cipher with the key of the length K. In addition you will get the table of the frequences of all pairs of letters of the language of the original text. Find such key (which does not have to be unique), for which the decoded text reaches the maximal sum of the frequences of the pairs of letters.

On the first line of the input there are two natural numbers K (K ≤ 5000) and N, where K denotes the length of the key and N denotes the number of the pairs of letters whose frequence is known. Then there follows N lines every containing two upper case of the english alphabet followed by one space and one integer F (F ≤ 10⁸), which is the value of the frequence of this pair of letters. If the pair is omitted, its frequency is considered to be a zero. This frequence is always positive integer. It holds that the higher the frequence is, the higher the probability of the occurence of that pair is. On the last line of the input, there is the encrypted text. This text consists only of the upper case from english alphabet. You can assume that the length of the text is smaller than 10000. The maximal sum of probabilities for the whole text is 10⁸.

On the only line of the output you should write the most probable key, by which the original text was encrypted. If there are more such keys, write the arbitrary one.

The input in the example corresponds to the original text HELLOIAMENCRYPTEDTEXT, which was encrypted by the key CPSPC. The overall probability of the key is 9.