After waiting for it to snow all week, it's finally the weekend, and Snow sees a brighter-than-usual light through her curtains. It's finally snowing!!, she yells as she throws them open. A blanket of white covers her driveway, indented only by two squirrel tracks. She checks her phone, and sees a message from her friend, Daniel.
Hey! I'm going skating, wanna come?? Find me at-
followed by a massive blurb of text.
It takes Snow a moment, but she realizes this is another one of Daniel's elaborate pranks! The street name has to be in the text somewhere... she thinks. After a couple minutes of reading, however, she can't seem to find a single street name. Snow thinks, then realizes: from her experience with Daniel, he might be at any rink whose street name is a subsequence of his message.
Snow knows of skating rinks nearby, each with a different address. Given Daniel's message, can you help Snow by summing the address numbers of every possible rink Daniel might be at?
Constraints
Address numbers are integers between and .
Street names will only contain lowercase letters.
Daniel's message only contains lowercase letters, spaces, and punctuation (.
, ,
, '
, !
, ?
).
Each street name is between and characters long.
Daniel's message is between and characters long.
Subtask 1 [50%]
Subtask 2 [50%]
Input Specification
The first line of input contains the integer .
The next lines each contain an address: an address number, followed by the street name.
The last line of input contains Daniel's message.
Output Specification
Output one integer, the sum of all possible address numbers Daniel could be at. Note the answer may not fit in a 32-bit integer.
Sample Input
3
20 tillplain
5555 sheppard
4980 yonge
yo since we've no place to go, let it snow! let it snow! let it snow! plain and simple...
Sample Output
5000
Sample Explanation
tillplain
and yonge
are subsequences of the message, whereas sheppard
is not.
Comments