23094번 - Pizzo Collectors 다국어

Lavish Circle (LC) is the fashionable circular avenue in the residential area of the town. Houses on LC are exceptionally expensive and some of them are currently empty. LC is under heavy control of the town mafia who wants to populate the empty houses with new owners loyal to the mafia. When LC is completely populated, each house owner will live in one house on LC. LC is a circular avenue of houses numbered from 1 to N, that is for i < N, i-th and i + 1-th houses are neighboring and also houses N and 1 are neighboring.

The house owners, both the existing ones and the new ones, fall into few categories according to the sum they can pay the mafia monthly for protecting them. The money is called pizzo and it is typically collected by a person called a pizzo collector (PC). The mafia employs a group of them.

The job of a PC is to go around entire LC exactly once in a month and collect pizzo from the selected houses on the journey. All selected houses on a journey of a PC must have owners of the same pizzo category. The journey must also start and end at the same house, it is a check PC completed the journey correctly. The pizzo is collected from this house only once, at the beginning or at the end of the journey. During his journey, a PC always moves forward by a fixed number of houses, until the PC arrives again to the starting house. That is, the number of houses a PC skips on each move is a non-negative integer d, which remains constant during the entire journey of this PC. It must hold that (d + 1) divides N evenly.

The mafia wants to employ as many PCs as possible. Of course, employing a number of PCs means that some owners quite probably have to pay pizzo more than once in a month, but the mafia does not care... Unfortunately, there is a complication. PCs are peaceful citizens and they do not tend to shoot at each other under normal conditions. However, when two PCs find out that at their respective collection journeys they visit the same set of houses, and it does not matter in which order they visit the houses, the collectors tend to shoot each other and thus attract the police, which is a behavior the mafia wants to avoid at any cost. So, no two collectors who may shoot each other can be employed simultaneously.

The total value of all collected pizzo depends also on the categories of the owners of the newly populated houses. The mafia decides on the category of each new house owner. Obviously the mafia wants to maximize their income. You have been hired as an analyst to find the maximum possible total value of all collected pizzo in one month, when LC gets completely and suitably populated. The mafia is going to decide on the pizzo category of each new house owner based on your recommendations. The number of houses on LC is a non-negative integer power of a prime number.

The first line contains integer N (1 ≤ N ≤ 10⁵), a non-negative integer power of some prime number p. The second row contains string S of length N, which consists of only capital letters of English alphabet and the character “?”. The characters of the string represent the houses on LC in the order they appear on LC. The “?” character represents a currently empty house, each of the other characters represent the pizzo category of the house owner.

The next line contains integer k (1 ≤ k ≤ 26), the number of different pizzo categories. Each of the next k lines contains an integer pair c_i a v_i, where c_i is a capital English character and 1 ≤ v_i ≤ 10⁶ is the money value which is paid by a house owner of pizzo category c_i in one visit of a PC to the house.

It is guaranteed that for every category that appears in S, there is a pair c_i and v_i which defines its money value which is paid on the PC’s visit.

Print the maximum possible total value of all collected pizzo in one month, when LC is completely populated.