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

Лавіш Сьоркл (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 буде повністю заселений.

Приклади