피조 수금원

Lavish Circle(LC)는 마을 주거 지역에 있는 세련된 원형 도로이다. LC에 있는 집들은 유난히 비싸고, 그중 일부는 현재 비어 있다. LC는 마피아가 철저히 관리하고 있으며, 마피아는 빈 집에 마피아에 충성하는 새 주인을 들이려 한다. LC가 완전히 채워지면 각 집 주인은 LC의 집 한 채에 살게 된다. LC는 1번부터 N번까지 번호가 붙은 집들이 원형으로 늘어선 도로이다. 즉 i < N일 때 i번째 집과 i + 1번째 집이 이웃하고, N번째 집과 1번째 집도 이웃한다.

기존 주인과 새 주인 모두 마피아에게 매달 보호비로 낼 수 있는 금액에 따라 몇 가지 범주로 나뉜다. 이 돈을 피조(pizzo)라고 부르며, 보통 피조 수금원(pizzo collector, PC)이라는 사람이 걷는다. 마피아는 여러 명의 수금원을 고용한다.

PC의 일은 한 달에 한 번 LC 전체를 정확히 한 바퀴 돌며 이동 중에 선택한 집들에서 피조를 걷는 것이다. 한 PC의 이동에서 선택된 모든 집은 같은 피조 범주의 주인이 있어야 한다. 이동은 같은 집에서 시작하고 끝나야 하며, 이는 PC가 이동을 제대로 마쳤는지 확인하기 위한 것이다. 이 집에서는 피조를 이동의 시작이나 끝 중 한 번만 걷는다. 이동하는 동안 PC는 항상 고정된 수의 집만큼 앞으로 나아가며, 시작한 집에 다시 도착할 때까지 이를 반복한다. 즉, PC가 매번 건너뛰는 집의 수는 음이 아닌 정수 d이며, 이 PC의 이동 전체에서 일정하게 유지된다. (d + 1)이 N을 나누어떨어져야 한다.

마피아는 가능한 한 많은 PC를 고용하려 한다. 물론 PC를 여러 명 고용하면 일부 주인이 한 달에 피조를 두 번 이상 낼 가능성이 크지만, 마피아는 신경 쓰지 않는다. 그런데 문제가 하나 있다. PC들은 평화로운 시민이라 보통은 서로 총을 쏘지 않는다. 그러나 두 PC가 각자의 수금 이동에서 같은 집합의 집들을 방문한다는 사실을 알게 되면, 집을 방문하는 순서와 상관없이 서로 총을 쏘는 경향이 있고, 이는 경찰의 이목을 끌기 때문에 마피아가 어떤 대가를 치르더라도 피하려는 행동이다. 따라서 서로 총을 쏠 수 있는 두 수금원을 동시에 고용할 수 없다.

걷힌 피조의 총액은 새로 채워진 집 주인들의 범주에도 달려 있다. 마피아는 새 집 주인 각각의 범주를 정한다. 당연히 마피아는 수입을 최대화하려 한다. 당신은 LC가 완전히 그리고 적절히 채워졌을 때 한 달 동안 걷을 수 있는 피조 총액의 최댓값을 구하는 분석가로 고용되었다. 마피아는 당신의 추천에 따라 새 집 주인 각각의 피조 범주를 정할 것이다. LC의 집 수는 소수의 음이 아닌 정수 거듭제곱이다.

첫째 줄에는 정수 N (1 ≤ N ≤ 105)이 주어지며, 이는 어떤 소수 p의 음이 아닌 정수 거듭제곱이다. 둘째 줄에는 길이 N의 문자열 S가 주어지며, 이는 영어 알파벳 대문자와 문자 “?”로만 이루어져 있다. 문자열의 각 문자는 LC에 나타나는 순서대로 집을 나타낸다. “?” 문자는 현재 비어 있는 집을 나타내고, 다른 각 문자는 그 집 주인의 피조 범주를 나타낸다.

다음 줄에는 정수 k (1 ≤ k ≤ 26)가 주어지며, 이는 서로 다른 피조 범주의 수이다. 다음 k개 줄 각각에는 정수 쌍 ci a vi가 주어지며, ci는 영어 대문자이고, 1 ≤ vi ≤ 106은 피조 범주 ci의 집 주인이 PC의 방문 한 번에 내는 금액이다.

S에 나타나는 모든 범주에 대해, PC의 방문 시 내는 금액을 정의하는 쌍 ci와 vi가 존재함이 보장된다.

LC가 완전히 채워졌을 때 한 달 동안 걷을 수 있는 피조 총액의 최댓값을 출력한다.