호연이는 심심해서 노래 한 곡을 만들었다. 그런데 음악이 뭔가 부족한 것 같아서 조금 수정하려고 한다. 호연이가 만든 곡은 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이다.

#2774 upload 20 done 9 how_to_reg 7

작곡1 timer 1s memory 64MB

#2774

작곡1 1s 64MB