금고 털기

금고 자물쇠는 N개의 회전판으로 이루어져 있다. 각 회전판에는 0부터 M-1까지의 번호가 원형으로 적혀 있으며, 번호가 M-1인 회전판을 한 칸 더 돌리면 0이 된다.

모든 회전판에 표시된 번호가 같아지면 금고가 열린다. 회전판은 번호가 커지는 방향으로만 돌릴 수 있고, 회전판 하나를 한 칸 돌리는 데 1초가 걸린다.

같은 번호를 가진 연속된 회전판들은 한꺼번에 돌릴 수 있다. 이때 구간의 길이와 관계없이 모두 한 칸 증가시키는 데 1초가 걸린다. 예를 들어 상태가 (1, 1, 1, 2)라면, 왼쪽의 회전판 3개를 함께 1초 동안 돌려 모두 2로 만들 수 있다.

초기 상태가 주어졌을 때, 금고를 열기 위해 필요한 최소 시간을 구하시오.

첫째 줄에 회전판의 개수 N과 번호의 가짓수 M이 주어진다. (1 ≤ N ≤ 500, 2 ≤ M ≤ 10,000)

둘째 줄에는 각 회전판의 초기 번호를 나타내는 N개의 정수가 주어진다.

금고를 열기 위해 필요한 최소 시간을 출력한다.

초기 상태가 (9, 0, 1, 0, 3)일 때 다음과 같이 조작할 수 있다.

• 초기 상태: (9, 0, 1, 0, 3)
• 1초 경과: (9, 0, 1, 1, 3)
• 2초 경과: (0, 0, 1, 1, 3)
• 3초 경과: (1, 1, 1, 1, 3)
• 4초 경과: (2, 2, 2, 2, 3)
• 5초 경과: (3, 3, 3, 3, 3)

따라서 이 경우 5초 만에 금고를 열 수 있다.