Pipeline Monitoring

A gas pipeline system consists of n nodes numbered from 1 to n. Node 1 is the central storage facility. For each node i (2 ≤ i ≤ n) there is a one‐way pipeline from node p_i to node i with a type represented by a lowercase English letter c_i (a–z). It is guaranteed that gas can flow from node 1 to every other node.

A special robot is used to inspect the pipelines. Before inspection the robot is placed at some node. Then it moves repeatedly along a pipeline (always following the gas flow direction) and finally it is removed from the system. This whole process is called one inspection session.

There are m different inspection specifications numbered 1…m. The k-th specification is a string st_k consisting of lowercase letters and has a cost w_k. If a session is carried out using specification k, then the robot makes exactly len(st_k) moves and for every move j (1 ≤ j ≤ len(st_k)), the type of the pipeline traversed in the j-th move must equal the j-th character of st_k.

Your task is to choose a collection of inspection sessions so that every pipeline (i.e. every edge from node p_i to node i for i = 2…n) is inspected at least once, and the total cost is minimized. In addition, you must output a valid plan specifying the sessions.

inputFormat

The input consists of:

1. A line containing two integers n and m — the number of nodes and the number of specifications.
2. A line containing n-1 integers: p₂, p₃, ..., p_n, where for each node i (2 ≤ i ≤ n), there is a pipeline from node p_i to node i.
3. A line containing a string of length n-1. The i-th character of this string (for i = 1…n-1) is c_i+1, the type of the pipeline from node p_i+1 to node i+1.
4. m lines follow. The k-th of these lines contains an integer w_k and a nonempty string st_k, representing the cost and the specification string for session type k.

You may assume that for every pipeline type that occurs in the system, there is at least one specification whose string is of length 1 and equals that letter.

outputFormat

On the first line, output the minimum total cost required to inspect all pipelines. On the second line, output an integer q — the number of inspection sessions in your plan. Then output q lines, each describing one session. For a session using specification t with pattern st_t (of length L), you should output L+1 space‐separated integers representing the nodes visited by the robot; the session must start at some node s and then follow L moves so that for each move the pipeline type exactly matches the corresponding character of st_t. You should also indicate the specification number used for that session. (The exact format of the session descriptions is up to you, as long as they specify a valid collection of sessions that achieve the minimum cost.)

If there exist several optimal answers, you may output any one of them.

sample

3 2
1 1
ab
5 a
6 b

11
2
1 1 2
2 1 3