문제
호연이는 심심해서 노래 한 곡을 만들었다. 그런데 음악이 뭔가 부족한 것 같아서 조금 수정하려고 한다. 호연이가 만든 곡은 N개의 파트로 이루어져 있고, 각 파트는 A~G, A7~G7, Am~Gm, Am7~Gm7 중 하나의 코드로 구성되어 있다. 한편, 화성학적으로 좋은 코드 쌍이 M개 있어서, 코드 Xi 와 Yi 가 서로 인접한 파트에 있으면(Xi 로 진행한 후 Yi 로 진행하거나 Yi 로 진행한 후 Xi 로 진행하는 경우) Hi 의 조화로움을 얻을 수 있다. M개의 코드 쌍을 제외한 나머지 코드 쌍들의 조화로움은 0이다.
음악의 조화로움은 인접한 두 파트의 조화로움들의 합으로 가정한다. 예를 들어 G-Cm, Am7-D, Cm-G7의 조화로움이 각각 10, 17, 14일 때, B-C7-D-Am7-G7-Cm-G로 진행하는 음악의 조화로움은 0+0+17+0+14+10=41이 된다.
호연이는 한 개의 파트를 선택해서 코드를 바꿔서 가장 조화로운 음악을 만들려고 한다. 호연이를 도와 무슨 파트를 바꿔야 하는지 구하는 프로그램을 작성하여라. 주의: 수정 전의 음악이 가장 조화롭다고 해도 코드를 반드시 바꿔야 한다.
<제약조건> • 전체 데이터의 20%는 N ≤ 50이다.
• 전체 데이터의 40%는 N ≤ 1,000이다.
입력
첫 번째 줄에는 음악의 파트 수 N과 코드 쌍의 수 M이 주어진다. (2 ≤ N ≤ 100,000, 0 ≤ M ≤ 378)
두 번째 줄에는 호연이가 만든 음악에서 각 파트의 코드가 차례대로 주어진다.
세 번째 줄부터 M개의 줄에는 Xi, Yi, Hi 가 주어진다. Xi, Yi는 문제에서 주어진 28개의 코드 중 하나이며, Hi 는 1,000 이하의 자연수이다.
출력
호연이가 수정한 후의 음악의 조화로움의 최댓값을 출력한다.
예제 #1
5 5
A A7 Am Am7 Cm
A Bm7 10
B C 15
Am Gm 7
A7 Am7 12
Cm Gm 6
13
예제 #2
3 1
C7 C7 C7
C7 C7 7
7
힌트
출처
functionx
로그인해야 코드를 작성할 수 있어요.