금고

바이트만은 오래된 금고에 전 재산을 보관한다. 이 금고의 자물쇠는 똑같이 생긴 바퀴 $n$개로 이루어져 있고, 각 바퀴에는 $m$개의 글자로 된 같은 단어가 빙 둘러 적혀 있다. 바퀴는 서로 독립적으로 돌릴 수 있어서, 각 바퀴를 $m$가지 위치 중 하나에 맞출 수 있다. $m$개의 모든 위치에서 모든 바퀴가 같은 글자를 보이면, 즉 모든 바퀴가 완전히 같은 단어를 나타내면 금고가 열린다.

바퀴 하나를 왼쪽이나 오른쪽으로 $360/m$도 돌리는 데는 $1$초가 걸린다. 금고를 여는 데 필요한 최소 시간을 구하여라.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다 ($2 \le n, m \le 1\,000\,000$). 각각 자물쇠에 달린 바퀴의 수와 각 바퀴에 적힌 단어의 길이를 뜻한다.

둘째 줄에 길이가 $m$인 단어 $s_1 s_2 \dots s_m$이 주어지며, 알파벳 대문자로만 이루어져 있다.

셋째 줄에 $n$개의 정수 $o_1, o_2, \dots, o_n$이 공백 하나로 구분되어 주어진다 ($0 \le o_i < m$). $o_i = k$는 $i$번째 바퀴가 기준 위치에서 왼쪽으로 $k$칸 돌아가 있다는 뜻이며, 이때 그 바퀴는 $s_{k+1} s_{k+2} \dots s_m s_1 s_2 \dots s_k$를 나타낸다. 예를 들어 $o_i = 0$이면 그 바퀴는 전혀 돌아가 있지 않다.

금고를 여는 데 필요한 최소 시간(초)을 정수 하나로 출력한다.

왼쪽으로 한 칸 돌리는 것과 오른쪽으로 한 칸 돌리는 것은 서로 반대 방향의 조작이다. 어떤 바퀴가 지금 OWIKSL을 나타내고 있다고 하자. 이 바퀴를 왼쪽으로 한 칸 돌리면 WIKSLO가 되고, 오른쪽으로 한 칸 돌리면 LOWIKS가 된다. 두 바퀴는 나타내는 단어가 완전히 같을 때에만 서로 맞춰진 것으로 본다. 따라서 단어에 반복되는 구조가 있으면 서로 다른 여러 회전이 같은 모습을 만들 수도 있다.