1366번 - 기타 코드

음악에서 음표는 다음과 같이 12개의 이름이 있다. 오름차순으로 A, A#, B, C, C#, D, D#, E, F, F#, G, G# 이다.

이 음은 이것보다 더 높아질 때, 낮아질 때, 모두 이 순서대로 다시 반복되기 때문에, G#보다 한음 높은 음은 A이고, B보다 다섯 음 낮은 음은 F#이다. 따라서, 어떤 음에서 12음 떨어진 음은 항상 자기 자신이 된다. 이 문제에서 같은 이름을 가지고 있으면, 옥타브와 상관없이 같은 음으로 생각한다.

기타는 여러 개의 줄을 가지고 있는 악기이고, 각 줄은 12개의 음 중 하나로 튜닝되어 있다. 각 줄에서 나는 소리를 열린 음이라고 한다. 줄의 아래에는 프렛이 있는데, 프렛은 1번 프렛부터 차례때로 번호가 있다. 프렛을 누르게 되면 줄의 음이 변하게 된다. 어떤 줄의 i번을 누르게 되면, 그 줄의 열린 음보다 i만큼 높은 음이 울린다.

예를 들어, 어떤 줄의 열린 음이 C#일 때, 3번 프렛을 누르고 그 줄을 친다면 E가 소리난다.

코드는 동시에 치는 음의 집합이다. 기타에서 코드를 치기 위해서, 각 줄은 코드에 있는 음 중 하나의 음을 반드시 소리 내야 한다. 그리고 코드에 있는 음 모든 음이 소리 나야 한다.

각 코드를 치는 방법은 여러 가지가 있다. 민식이는 코드를 치는 난이도를 손을 얼마나 뻗느냐로 매기려고 한다. 프렛을 누른 줄 중 가장 높은 프렛의 번호에서 가장 낮은 프렛의 번호를 뺀 후에 1을 더하면 그것이 그 코드의 난이도이다. 이때, 반드시 프렛을 누른 줄만 계산에 포함시켜야 한다. 따라서, 프렛을 누르지 않은 열린 줄의 경우에는 코드의 난이도에 영향을 미치지 않는다. 만약 어떤 코드가 프렛을 누르지 않고 칠 수 있다면, 그 코드의 난이도는 0이 된다.

기타의 줄의 개수 N, 각 줄이 무슨 음으로 튜닝되어 있는지가 주어진다. 그 때, 코드를 구성하는 음이 주어질 때, 그 코드의 가능한 난이도 중 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 N과 M이 주어진다. N은 기타의 줄의 개수이고, M은 코드를 구성하는 음의 개수이다. 둘째 줄에는 각 줄이 무슨 음으로 튜닝되어 있는지를 나타내는 N개의 음이 주어지고, 셋째 줄에는 각 코드를 구성하는 M개의 음이 주어진다. 코드를 구성하는 음은 중복되지 않으며, 음은 모두 문제의 초반에 나온 12개의 음만 주어진다.

첫째 줄에 가능한 난이도 중 최솟값을 출력한다.

• 1 ≤ M ≤ N ≤ 6

예제 1의 경우

• 1번 줄 (E): 프렛을 누르지 않는다. E를 연주한다.
• 2번 줄 (A): 2번 프렛을 누른다. B를 연주한다.
• 3번 줄 (D): 2번 프렛을 누른다. E를 연주한다.
• 4번 줄 (G): 1번 프렛을 누른다. G#을 연주한다.
• 5번 줄 (B): 프렛을 누르지 않는다. B를 연주한다.
• 6번 줄 (E): 프렛을 누르지 않는다. E를 연주한다.

따라서 답은 (2-1)+1 = 2이다.