Board Game

A player starts with N cards. The front of the cards is numbered from 1 to N in order, and the back of each card is colored red (R), green (G), or blue (B).

The player starts in village 1. On each move, the player must move from the current village to an adjacent village connected by a road, and must use the remaining card with the smallest number. Each road is also colored R, G, or B. If the color of the used card matches the color of the road taken, the player earns 10 points. The same village or road may be visited multiple times.

Find the maximum score obtainable after using all cards in numbered order.

The first line contains the number of cards N. The second line contains the colors of the N cards in numbered order, separated by spaces.

The third line contains the number of villages M and the number of roads K, separated by a space. Each of the next K lines contains the two endpoint village numbers of a road and the road color, separated by spaces.

There is at most one road directly connecting any pair of villages. N is a positive integer at most 1,000, M is a positive integer at most 500, and K is a positive integer at most 10,000. Every card color and road color is one of R, G, and B.

Print the maximum score obtainable in the board game on the first line.