Програмчлалын олимпиадын бодлогын архив

Зарим биологийн объектуудын бүтцийг элементүүдийнх нь дарааллаар илэрхийлж болно. Элементүүдийг том үсгээр тэмдэглэнэ. Биологичид урт дарааллыг богиносгохыг хичээдэг. Богино дарааллуудыг деталиуд гэнэ. Хэрэв P гэсэн олонлогт p₁, ..., p_n деталиуд байгаад тэдгээрийг p₁, ..., p_n гэж залгахад үүссэн дараалал нь S-тэй тэнцүү бол S-ийг P-д байгаа деталиудаас тогтсон гэж үзнэ. p₁, ..., p_n деталиудыг залгана гэдэг нь тэдгээрийг хооронд нь хоосон зай хэрэглэлгүйгээр нийлүүлэхийг хэлнэ. Аль нэг деталь дараалалд нэгээс олон удаа орж болох ба дараалалд заавал бүх деталь агуулагдах албагүй. Жишээ нь ABABACABAAB дарааллыг дараах олонлогийн деталиудаар дүрсэлж болно:
{A, AB, BA, CA, BBC}.
S-ийн эхний К үсгийг S-ийн К урттай префикс гэж нэрлэнэ. Таны програм оролт болгож деталиудын олонлог Р, элементүүдийн дараалал Т-г авна. Р дэх деталиудыг ашиглан үүсгэж болох префиксийн боломжит хамгийн их утгыг ол.

Input

Оролтын хоёр хэсгээс тогтно. Эхний хэсэгт нь деталиудын олонлог Р-г тодорхойлсон байх бол дараагийн хэсэгт нь дараалал Т өгөгднө. Оролтын эхний мөрөнд Р олонлогт байх деталиудын тоо N (1<=N<=100) байрлана. Үүний дараа деталь бүрийг хоёр мөрөөр илэрхийлнэ. Эхний мөрөнд нь уг деталийн урт L (1<=L<=20) тоо байна. Дараагийн мөрөнд нь L урттай, том үсгүүдээс ('A'-гаас 'Z' хүртлэх) тогтох тэмдэгт мөр байна. N ширхэг деталиуд бүгд ялгаатай байна.
Деталиудын дараа дараалал Т өгөгдөнө. Уг дарааллын үсэг бүр нь нэг нэг мөрөнд өгөгдөх ба хамгийн сүүлийн мөрөнд цэг байна. Дарааллын урт нь нэгээс 500 000 хүртэл байж болно.

Output

Гаралт дээр Р олонлогийн деталиудыг ашиглан үүсгэж болох Т-гийн боломжит префиксүүдийн хамгийн их утгыг хэвлэнэ.

Example

Input:
5                  
1                                                     
A                                                     
2                                                     
AB                                                    
3                                                     
BBC                                                   
2                                                     
CA                                                    
2                                                     
BA     
A                          
B                                   
A                                   
B                                   
A                                   
C                                   
A                                   
B                                   
A                                   
A                                   
B                                   
C                                   
B                                   
.       
Output:
11