파이프 모니터링

한 지역의 가스 배관 시스템은 다음과 같이 구성되어 있다. 노드는 1부터 $n$까지 번호가 붙어 있고, 일부 노드는 단방향 파이프로 연결되어 있다. 1번 노드는 중앙 가스 저장소이다. 이 시스템은 $p_2, p_3, ..., p_n$ 값으로 표현된다. 2부터 $n$까지의 모든 $i$에 대해 노드 $p_i$에서 노드 $i$로 가는 단방향 파이프가 하나 있고, 가스는 $p_i$에서 $i$로 흐른다. 중앙 저장소에서 어떤 노드로든 가스를 보낼 수 있으며, 중간 노드를 거쳐도 된다. 파이프에는 'a'부터 'z'까지 소문자로 표시되는 종류가 있다. $p_i$에서 $i$로 가는 파이프의 종류는 $c_i$이다.

로봇을 노드 하나에 놓으면 로봇이 파이프를 따라 이동하면서 지나가는 파이프를 검사한다. 로봇은 가스가 흐르는 방향으로만 이동할 수 있다. 한 번 이상 이동한 뒤 로봇을 시스템에서 꺼낸다.

각 실행은 1부터 $m$까지 번호가 붙은 $m$개의 명세 중 하나와 일치해야 한다. 명세 $k$는 소문자로 이루어진 문자열 $s_k$이다. 실행이 $s_k$와 일치한다는 것은 로봇이 정확히 $|s_k|$번 이동하고, $j$번째 이동에서 지나간 파이프의 종류가 $s_k$의 $j$번째 문자와 같다는 뜻이다. 명세 $k$와 일치하는 실행의 비용은 $w_k$이다.

모든 파이프를 검사해야 하며, 로봇은 여러 번 실행해도 된다. 각 실행마다 명세와 그 명세에 맞는 경로를 고른다. 모든 파이프를 검사하면서 총 비용이 최소가 되도록 하라. 같은 파이프를 여러 번 검사해도 된다.

첫 줄에 세 정수 $n$, $m$, $t$가 주어진다. 각각 노드 수, 명세 수, 0 또는 1의 값을 가지는 플래그이다. 단, $1 \le n \le 500$, $1 \le m \le 10^5$이다. 다음 $n-1$개의 줄에는 공백으로 구분된 $p_i$와 $c_i$가 주어진다. $p_i$는 노드 $i$로 가는 파이프의 시작 노드이고($1 \le p_i \le i-1$), $c_i$는 그 파이프의 소문자 종류이다. 다음 $m$개의 줄에는 정수 $w_i$($1 \le w_i \le 10^9$)와 공백으로 구분된 소문자 문자열 $s_i$가 주어진다. $w_i$는 명세 $i$와 일치하는 실행의 비용이다. 모든 문자열 $s_i$의 길이 합은 $10^6$을 넘지 않는다.

첫 줄에는 모든 파이프를 검사하는 실행들의 최소 총 비용을 출력한다. 모든 파이프를 검사할 수 없으면 -1을 출력한다. $t = 0$이면 더 이상 출력하지 않는다.

$t = 1$이고 검사가 가능하면, 둘째 줄에 실행 횟수 $k$를 출력한다. 이어지는 $k$개의 줄에는 세 정수 $a_i$, $b_i$, $c_i$를 출력한다. 각각 실행 $i$가 시작하는 노드, 끝나는 노드, 일치하는 명세 번호이다. 최적 방법이 여러 개이면 그중 아무거나 출력해도 된다.

두 번째 예제의 파이프 시스템과 모든 파이프를 검사하는 최적 방법은 아래 그림과 같다.

다음 사항에 주의한다.

같은 파이프를 여러 번 검사할 수 있다. 예시에서는 2번 노드에서 3번 노드로 가는 파이프를 두 번 검사했다.

같은 명세를 여러 번 사용할 수 있다. 예시에서는 2번 명세를 두 번 사용해서 1번에서 6번으로 가는 경로와 6번에서 7번으로 가는 경로를 검사했다.

로봇은 가스가 흐르는 방향으로만 이동할 수 있다. 로봇은 2번 노드에서 1번 노드로 이동할 수 없으므로, 명세 'ab'는 2에서 1을 거쳐 6으로 가는 경로에 쓸 수 없다.