Description

In front of "juruo" HansBug is an English essay. However, with his anxious IQ, HansBug has already scribbled a draft. He then notices there are still $40$ minutes left before the exam ends, so he decides to estimate the "value" (also called "gold content") of this English essay, which contains $M$ words in total. As we all know, using advanced vocabulary in English essays for entrance exams can effectively raise the essay’s "gold content", thus earning a better score. It is known that "juruo" HansBug knows $N$ advanced words, denoted as $A_i$ (each word has length $L_i$ and consists of digits and letters in both uppercase and lowercase). The "gold content" value of this advanced word is $B_i$, meaning every occurrence of this word increases the total value by $B_i$. But his brain cells and RP ("luck") are already exhausted, so this great task is left to you!

Input Format

• The first line contains two positive integers $N$ and $P$, where $N$ is the number of advanced words HansBug knows, and $P$ is the modulus.
• The next $N$ lines each contain a word $A_i$ (of length $L_i$) and an integer $B_i$, where $B_i$ satisfies $0 < B_i \le 10^5$, representing the value of that word.
• The following lines until the end of input form an English essay, which contains $M$ words in total, along with some separators (the separators include and only include ,, ., !, ?).

Output Format

Output one line containing a single integer: the total value of the essay modulo $P$.

5 99
hansbug 1
kkksc03 2
yyy 3
absi2011 4
lzn 100
hansbug is a juruo!but absi2011 not.!?!
one day absi2011 laughed at yyy and hansbug.
then kkksc03 and lzn blamed him for that.

16

5 99
yyyy 1
kkksc03 2
yyy 3
absi2011 4
lzn 100
yyyy is a juruo!but absi2011 not.!?!
one day absi2011 laughed at yyy and yyyy.
then kkksc03 and lzn blamed him for that.

16

Hint

In sample $1$, there are $2$ occurrences of hansbug, $2$ of absi2011, $1$ of yyy, $1$ of kkksc03, and $1$ of lzn, so the total value is $1 \times 2 + 2 \times 4 + 3 \times 1 + 4 \times 1 + 100 \times 1 = 115$, and $115 \bmod 99 = 16$.

In sample $2$, it is basically the same as sample $1$. Note that the whole yyyy cannot be considered as yyy appearing $2$ times. Please note this is an English essay; treat the word as the smallest unit.

This problem is case-sensitive.

Constraints (let the maximum length of all words be $\rm{Lmax}$):

For all testdata, $1 \le N \le 10^5$, $1 \le M \le 3 \times 10^4$, $1 \le P \le 10^9$.

Translated by ChatGPT 5