LCC '23 Contest 3 S2 - Let It Snow

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

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 N 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 1 and 10^6.

Street names will only contain lowercase letters.

Daniel's message only contains lowercase letters, spaces, and punctuation (., ,, ', !, ?).

Each street name is between 1 and 100 characters long.

Daniel's message is between 1 and 10^5 characters long.

Subtask 1 [50%]

1 \le N \le 100

Subtask 2 [50%]

1 \le N \le 10^5

Input Specification

The first line of input contains the integer N.

The next N 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

There are no comments at the moment.