Коллекционеры Пиццо

Лавиш Сёркл (LC) — это модная круговая улица в жилом районе города. Дома на LC исключительно дорогие, и некоторые из них в настоящее время пустуют. LC находится под жёстким контролем городской мафии, которая хочет заселить пустующие дома новыми владельцами, лояльными мафии. Когда LC будет полностью заселён, каждый владелец будет жить в одном из домов на LC. LC представляет собой круговую улицу, на которой дома пронумерованы от $1$ до $n$, то есть для $i<n$, $i$-й и $(i+1)$-й дома являются соседними, и также соседними являются дома $n$ и $1$.

Владельцы домов, как текущие, так и новые, делятся на несколько категорий в зависимости от суммы, которую они могут ежемесячно выплачивать мафии за защиту. Эти деньги называются пиццо, и обычно их собирает человек под названием сборщик пиццо (PC). Мафия нанимает группу таких сборщиков.

Работа PC заключается в том, чтобы обходить весь LC ровно один раз в месяц и собирать пиццо из выбранных домов на своём маршруте. Все выбранные дома на маршруте PC должны иметь владельцев одной и той же категории пиццо. Маршрут также должен начинаться и заканчиваться в одном и том же доме, что служит проверкой того, что PC завершил маршрут правильно. Пиццо с этого дома собирается только один раз — либо в начале, либо в конце маршрута. Во время своего маршрута PC всегда перемещается на фиксированное количество домов вперёд, пока снова не вернётся в начальный дом. То есть, количество домов, которые PC пропускает при каждом перемещении, является неотрицательным целым числом $d$, которое остаётся постоянным на протяжении всего маршрута данного PC. При этом $(d+1)$ должно делить $n$ нацело.

Мафия хочет нанять как можно больше сборщиков PC. Конечно, нанять несколько PC означает, что некоторым владельцам, вероятно, придётся платить пиццо больше одного раза в месяц, но мафию это не беспокоит… Однако возникает осложнение. Сборщики PC — мирные граждане и обычно не стреляют друг в друга. Но если два PC обнаружат, что на своих маршрутах они посещают одинаковые дома, независимо от порядка их посещения, они могут начать стрелять друг в друга и тем самым привлекут полицию, что мафия хочет избежать любой ценой. Таким образом, два сборщика, которые могут вступить в конфликт, не могут быть наняты одновременно.

Общая сумма всех собранных пиццо также зависит от категорий владельцев вновь заселённых домов. Мафия определяет категорию каждого нового владельца дома. Очевидно, мафия хочет максимизировать свои доходы. Вы были наняты в качестве аналитика, чтобы найти максимально возможную общую сумму всех собранных пиццо за один месяц, когда LC будет полностью и оптимально заселён. Мафия собирается определить категорию пиццо для каждого нового владельца дома на основе ваших рекомендаций. Количество домов на LC является неотрицательной целой степенью простого числа.

Входные данные

Первая строка содержит целое число $n(1\le n\le 10^5)$ — неотрицательную целую степень простого числа $p$. Вторая строка содержит строку $s$ длины $n$, которая состоит только из заглавных букв английского алфавита и символа "?". Символы строки представляют дома на LC в порядке их расположения на LC. Символ "?" обозначает пустующий в данный момент дом, каждый из остальных символов представляет категорию пиццо владельца дома.

Следующая строка содержит целое число $k(1\le k\le 26)$ — количество различных категорий пиццо. Каждая из следующих $k$ строк содержит пару чисел $c_i$ и $v_i$, где $c_i$ — заглавная английская буква, а $1\le v_i\le 10^6$ — сумма денег, которую платит владелец дома категории пиццо $c_i$ за один визит PC.

Гарантируется, что для каждой категории, которая встречается в $s$, существует пара $c_i$ и $v_i$, определяющая её денежную стоимость, которая выплачивается при визите PC.

Выходные данные

Выведите максимально возможную общую сумму всех собранных пиццо за один месяц, когда LC будет полностью заселён.

Примеры