$n$개의 징검다리가 있다. $i$번째 징검다리는 점프 비용 $w_i$를 갖는다. 당신은 현재 $1$번 징검다리에 있고, 징검다리들을 적절히 거쳐 $n$번 징검다리로 건너 가려고 한다. 징검다리를 건너는 규칙은 구체적으로 다음과 같다.

• $i$번째 징검다리에서는 번호가 증가하는 방향으로 최대 $k$ 만큼 점프할 수 있다. 이때 점프한 거리를 $d$라고 할 때, $w_i \times d$의 비용이 발생한다.
• 예를 들어 $i = 3$, $k = 3$, $w_3 = 3$ 이라면 $3, 6, 9$의 비용을 지불한 뒤 $4, 5, 6$번 징검다리 중 한 곳으로 점프할 수 있다.

$w_1, w_2, ... , w_{n-1}$이 주어졌을 때, $1$번 징검다리에서 $n$번 징검다리에 도착하기 위해 지불해야 하는 최소 비용을 구해보자.

첫째 줄에 징검다리의 수 $n$과 점프 가능 범위 $k$가 공백으로 구분되어 주어진다. $(1 ≤ k < n ≤ 2,000)$

둘째 줄에 $w_1, w_2, ... , w_{n-1}$이 공백으로 구분되어 주어진다. $(1 ≤ w_i ≤ 1,000)$