Pizzo Kolleksiyaçıları

Лавиш Sörkl (LC) — şəhərin dəbdəbəli dairəvi küçəsində yerləşən bir yaşayış məhəlləsidir. Buradakı evlər çox bahalıdır və bəziləri hazırda boşdur. LC, şəhər mafiyasının ciddi nəzarəti altındadır və onlar boş evləri mafiyaya sadiq yeni sahiblərlə doldurmaq istəyirlər. LC tam məskunlaşdıqda, hər bir sahib LC-dəki evlərdən birində yaşayacaq. LC, evlərin $1$-dən $n$-ə qədər nömrələndiyi dairəvi küçədir, yəni $i<n$ üçün $i$-ci və $(i+1)$-ci evlər qonşudur və həmçinin $n$ və $1$ evləri də qonşudur.

Evlərin sahibləri, həm cari, həm də yeni, mafiya üçün aylıq ödəyə biləcəkləri məbləğə görə bir neçə kateqoriyaya bölünürlər. Bu pullar pizzo adlanır və adətən pizzo yığan (PC) adlı şəxs tərəfindən toplanır. Mafia belə yığıcılar qrupunu işə götürür.

PC-nin işi hər ay LC-ni dəqiq bir dəfə gəzmək və marşrutundakı seçilmiş evlərdən pizzo toplamaqdır. PC-nin marşrutundakı bütün seçilmiş evlər eyni pizzo kateqoriyasına malik sahiblərə sahib olmalıdır. Marşrut həmçinin eyni evdə başlayıb bitməlidir, bu da PC-nin marşrutu düzgün tamamladığını yoxlamaq üçün xidmət edir. Bu evdən pizzo yalnız bir dəfə toplanır — ya marşrutun əvvəlində, ya da sonunda. Marşrut zamanı PC həmişə eyni sayda ev irəliləyir, ta ki yenidən başlanğıc evinə qayıdana qədər. Yəni, PC-nin hərəkət edərkən keçdiyi evlərin sayı qeyri-mənfi tam ədəd $d$-dir və bu, həmin PC-nin marşrutu boyunca sabit qalır. Bu halda $(d+1)$ $n$-i tam bölməlidir.

Mafia mümkün qədər çox PC işə götürmək istəyir. Təbii ki, bir neçə PC işə götürmək bəzi sahiblərin ehtimal ki, ayda bir dəfədən çox pizzo ödəməli olacağı anlamına gəlir, amma mafiyanı bu narahat etmir... Lakin bir çətinlik yaranır. PC yığıcıları dinc vətəndaşlardır və adətən bir-birinə atəş açmırlar. Lakin iki PC marşrutlarında eyni evləri ziyarət etdiklərini aşkar etsələr, ziyarət sırasından asılı olmayaraq, bir-birinə atəş aça bilərlər və beləliklə, mafiyanın hər hansı bir qiymətə qarşısını almaq istədiyi polisi cəlb edərlər. Beləliklə, münaqişəyə girə biləcək iki yığıcı eyni vaxtda işə götürülə bilməz.

Bütün toplanan pizzo məbləği də yenidən məskunlaşan evlərin sahiblərinin kateqoriyalarından asılıdır. Mafia hər yeni ev sahibinin kateqoriyasını müəyyən edir. Aydındır ki, mafia gəlirlərini maksimuma çatdırmaq istəyir. Siz analitik olaraq işə götürülmüsünüz ki, LC tam və optimal şəkildə məskunlaşdıqda bir ay ərzində toplanan bütün pizzo məbləğinin maksimum mümkün ümumi məbləğini tapasınız. Mafia yeni ev sahibinin pizzo kateqoriyasını sizin tövsiyələriniz əsasında müəyyən edəcək. LC-dəki evlərin sayı sadə ədədin qeyri-mənfi tam dərəcəsidir.

Giriş verilənləri

Birinci sətir $n(1\le n\le 10^5)$ tam ədədini ehtiva edir — sadə ədəd $p$-nin qeyri-mənfi tam dərəcəsi. İkinci sətir yalnız böyük ingilis əlifbası hərflərindən və "?" simvolundan ibarət uzunluğu $n$ olan $s$ sətrini ehtiva edir. Sətirin simvolları LC-dəki evləri onların LC-dəki yerləşmə sırasına görə təmsil edir. "?" simvolu hazırda boş olan evi göstərir, qalan hər bir simvol isə ev sahibinin pizzo kateqoriyasını təmsil edir.

Növbəti sətir $k(1\le k\le 26)$ tam ədədini ehtiva edir — müxtəlif pizzo kateqoriyalarının sayı. Növbəti $k$ sətirin hər biri $c_i$ və $v_i$ cütlüyünü ehtiva edir, burada $c_i$ böyük ingilis hərfi, $1\le v_i\le 10^6$ isə PC-nin bir ziyarəti üçün ev sahibinin ödədiyi məbləğdir.

Zəmanət verilir ki, $s$-də rast gəlinən hər bir kateqoriya üçün onun PC ziyarəti zamanı ödənilən pul dəyərini müəyyən edən $c_i$ və $v_i$ cütlüyü mövcuddur.

Çıxış verilənləri

LC tam məskunlaşdıqda bir ay ərzində toplanan bütün pizzo məbləğinin maksimum mümkün ümumi məbləğini çıxarın.

Nümunələr