피아노 연주

시간 제한2초메모리 제한512 MB

요약

간격이 K인 N개의 손가락에 M개의 음을 배정해 인접한 음 사이 난이도의 최댓값을 최소로 만들고, 그 최솟값을 출력한다.

문제

N개의 손가락을 가진 세빈이는 한 손만으로 모든 곡을 연주하는 최고의 피아니스트다.

세빈이의 이웃한 두 손가락 사이의 거리는 K로 일정하다. 따라서 i번째 손가락과 첫 번째 손가락 사이의 거리를 Xᵢ라 하면 Xᵢ = (i-1)K가 성립한다(1 ≤ i ≤ N).

세빈이는 M개의 음으로 이루어진 곡을 연주하려 한다. 각 음을 어떤 손가락으로 연주하느냐에 따라 곡이 쉬워질 수도, 어려워질 수도 있다.

i번째 음의 음높이를 Pᵢ라 하고, 이 음을 Fᵢ번째 손가락으로 연주한다 하자. i번째 음과 이웃한 (i+1)번째 음을 연주할 때의 난이도는 |(Pᵢ₊₁ - Pᵢ) - (X_Fᵢ₊₁ - X_Fᵢ)|다.

곡의 난이도는 이웃한 두 음을 연주할 때의 난이도의 최댓값으로 정의한다. 각 음을 어떤 손가락으로 연주할지 정해 곡의 난이도를 최소로 만드는 프로그램을 작성하시오.

첫 번째 줄에 세빈이의 손가락 수와 곡을 이루는 음의 수를 나타내는 두 자연수 N과 M, 이웃한 두 손가락 사이의 거리를 나타내는 자연수 K가 공백을 두고 주어진다.

두 번째 줄에는 M개의 정수 P₁, ..., P_M이 공백을 두고 주어진다.

첫 번째 줄에 곡의 난이도의 최솟값을 출력한다.

모든 입력 데이터는 다음 조건을 만족한다.