탑 오르기

여러 발판을 뛰어넘어 탑의 꼭대기에 도달해야 하는 게임을 빠르게 클리어하는 중입니다. 탑은 같은 간격으로 배치된 여러 층으로 이루어져 있고, 각 층에는 발판이 하나씩 있습니다. 발판은 점으로 볼 수 있을 만큼 좁습니다. 강화 수준에 따라 캐릭터는 한 번의 점프로 최대 $k$ 층까지 올라갈 수 있습니다. 한 점(발판)에서 다른 점으로 점프하는 데 걸리는 시간은 다음 식으로 정의됩니다.

$\text{Time}((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + (y_1 - y_2)^2$

여기서 $x_1$과 $x_2$는 점프의 출발 발판과 도착 발판의 x 좌표이고, $y_1$과 $y_2$는 각각 출발 발판과 도착 발판이 있는 층입니다. 층은 1부터 차례로 번호가 매겨지므로 위로 갈수록 y 좌표가 1, 2, 3, ...으로 늘어납니다. 시간 공식과 그림에서 보듯이 가까운 층으로 점프하는 시간은 먼 층으로 점프하는 시간보다 짧습니다.

첫 번째 층에서 출발해 마지막 층에 도착합니다. 이 전략이 시간 측면에서 최적인지 확인하려고 합니다. 각 발판의 x 좌표와 점프할 수 있는 최대 높이가 주어질 때, 탑의 꼭대기에 도달하는 데 필요한 최소 시간을 구하세요.

첫 줄에 두 정수 $n$ ($2 \le n \le 20{,}000$)과 $k$ ($1 \le k \le 8$)가 주어집니다. $n$은 층의 개수이고, $k$는 한 번에 점프할 수 있는 최대 층 수입니다. 이어지는 $n$개의 줄에는 발판의 x 좌표를 나타내는 1 이상 1,000,000,000 이하의 정수가 한 줄에 하나씩 주어집니다. 발판은 출발점에서 끝점까지 탑을 올라가는 순서로 나열되어 있습니다. y 좌표는 1, 2, 3, ...으로 정해져 있어서 입력에 따로 주어지지 않습니다.

가장 아래의 (첫 번째) 발판에서 가장 위의 (마지막) 발판에 도달할 때까지 걸리는 총 시간을 출력하세요.