보드게임
시간 제한1초메모리 제한128 MB
색이 정해진 카드 순서와 색이 있는 그래프가 주어질 때, 1번 마을에서 시작해 카드를 순서대로 사용하며 도로 색과 일치시켜 얻는 점수를 최대화하는 문제입니다.
문제
플레이어는 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 중 하나이다.
출력
보드게임에서 받을 수 있는 최대 점수를 첫째 줄에 출력한다.