String Formation with Mandatory and Optional Substrings

You are given a target string T and m substrings. Each substring is associated with a flag: a flag of 1 indicates that the substring is mandatory and must appear in T (in any order), while a flag of 0 indicates that the substring is optional and can be used to completely reconstruct the remaining characters of T after removing all mandatory substrings.

The task is to determine if it is possible to form the target string by first removing each mandatory substring (if present) from T (in the order they are provided) and then checking if the leftover string can be segmented completely by concatenating some or all of the optional substrings. If both conditions are met, output YES; otherwise, output NO.

Note: When removing a mandatory substring, remove its first occurrence from the current target string.

inputFormat

The input is given via standard input (stdin) in the following format:

T
m
flag1 substring1
flag2 substring2
...
flagm substringm

Where:

• T is the target string.
• m is an integer representing the number of available substrings.
• Each of the next m lines contains an integer flag (either 0 or 1) and a substring, separated by space. A flag of 1 marks the substring as mandatory, while 0 marks it as optional.

outputFormat

Output a single line to standard output (stdout) containing either YES if the target string can be formed according to the rules described, or NO otherwise.

helloworld
3
1 hello
1 world
0 er

YES