보드게임

플레이어는 N장의 카드를 가지고 시작한다. 각 카드의 앞면에는 1번부터 N번까지의 번호가 순서대로 적혀 있고, 뒷면에는 빨간색(R), 녹색(G), 파란색(B) 중 하나가 칠해져 있다.

플레이어는 1번 마을에서 출발한다. 한 번 이동할 때마다 현재 마을과 길로 연결된 이웃 마을로 이동해야 하며, 이동할 때마다 남은 카드 중 번호가 가장 작은 카드를 한 장 사용한다. 각 길에도 R, G, B 중 하나의 색이 칠해져 있다. 사용한 카드의 색과 지나간 길의 색이 같으면 10점을 얻는다. 같은 마을이나 같은 길을 여러 번 지나도 된다.

모든 카드를 번호 순서대로 사용했을 때 받을 수 있는 최대 점수를 구하시오.

첫째 줄에 카드의 수 N이 주어진다. 둘째 줄에는 N장의 카드 색깔이 번호 순서대로 공백으로 구분되어 주어진다.

셋째 줄에는 마을의 수 M과 길의 수 K가 공백으로 구분되어 주어진다. 이어지는 K개의 줄에는 길의 양 끝 마을 번호와 길의 색깔이 공백으로 구분되어 주어진다.

두 마을을 직접 잇는 길은 최대 하나이다. N은 1,000 이하의 자연수, M은 500 이하의 자연수, K는 10,000 이하의 자연수이다. 카드와 길의 색깔은 R, G, B 중 하나이다.

보드게임에서 받을 수 있는 최대 점수를 첫째 줄에 출력한다.