시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB6964120.000%

문제

저명한 물리학자 리처드 파인만은 원자폭탄 제조의 비밀을 기록한 서류가 금고에 보관되어 있음을 알고, 이것을 훔쳐내고자 마음먹었다. 그는 자신의 금고털이 경험에 근거하여 금고 자물쇠의 동작방식을 알아내는데 성공하였다.

자물쇠는 N개의 회전판으로 이루어져 있으며, 각각의 회전판에는 그 둘레를 따라 0부터 M-1까지 총 M개의 번호가 표시되어 있다. 모든 회전판의 번호가 서로 같아지면 금고가 열린다. 모든 회전판은 한쪽 방향(번호가 커지는 방향)으로만 돌릴 수 있다. M-1인 상태에서 한차례 돌리고 나면 그 회전판의 번호는 0이 된다.

회전판 한 개를 돌려서 번호를 1만큼 증가시키는 데 1초가 걸린다. 그런데 파인만은 손가락이 매우 길어서 같은 번호를 가지는 연속된 회전판들을 한꺼번에 돌릴 수 있다. 예를 들어, 자물쇠의 상태가 (1, 1, 1, 2)일 때, 왼쪽 회전판 3개를 1초 만에 돌려서 모두 2로 만들 수 있다.

자물쇠의 초기 상태가 주어졌을 때, 금고를 열 수 있는 최단 시간을 구하시오.

입력

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

둘째 줄에는 N개의 회전판마다 초기 상태에서의 번호가 주어진다.

출력

금고를 열 수 있는 최단 시간을 출력한다.

예제 입력 1

5 10
9 0 1 0 3

예제 출력 1

5

힌트

  • 초기상태: (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)
  • 6초 경과. 작업 완료.