問題文

$N$ 個の星があり、星には $1, 2, …, N$ の番号がついています。

惑星探査機 MMA は番号 $1$ の星におり、以下の行動を何度でも繰り返すことができます。

• MMA がいる星の番号を $i$ とすると、$| i - j | \leq K$ であるような $1$ から $N$ の整数 $j$ を選び、番号 $j$ の星へ移動する。 ただし、移動するのには $A_j$ のコストがかかる。

MMA が星 $N$ に移動するためのコストの最小値を求めてください。

制約

• $2 \leq N \leq 10^{5}$
• $1 \leq K \leq N - 1$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

出力

問題の答えを一行に出力せよ。

入出力例

9 2
1 4 1 5 9 2 6 5 3

16

以下のように移動を行うことが最適です。

• 星 $1$ から 星 $3$ へ移動する。このとき、$1$ のコストがかかる。
• 星 $3$ から 星 $4$ へ移動する。このとき、$5$ のコストがかかる。
• 星 $4$ から 星 $6$ へ移動する。このとき、$2$ のコストがかかる。
• 星 $6$ から 星 $8$ へ移動する。このとき、$5$ のコストがかかる。
• 星 $8$ から 星 $9$ へ移動する。このとき、$3$ のコストがかかる。

コストの合計は $1 + 5 + 2 + 5 + 3 = 16$ で、これより小さくすることはできません。

12 3
326615242 28981601 905966046 301631327 545845778 686337330 591296755 22303272 975545757 351883807 834610553 377495877

1326510335