問題文

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

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

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

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

制約

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

入力

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

NNKK
A1A_1A2A_2   . . .   ANA_N

出力

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

入出力例

入力例1
9 2
1 4 1 5 9 2 6 5 3
出力例1
16

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

  • 11 から 星 33 へ移動する。このとき、11 のコストがかかる。
  • 33 から 星 44 へ移動する。このとき、55 のコストがかかる。
  • 44 から 星 66 へ移動する。このとき、22 のコストがかかる。
  • 66 から 星 88 へ移動する。このとき、55 のコストがかかる。
  • 88 から 星 99 へ移動する。このとき、33 のコストがかかる。

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

入力例2
12 3
326615242 28981601 905966046 301631327 545845778 686337330 591296755 22303272 975545757 351883807 834610553 377495877
出力例2
1326510335

Submit


Go (1.21)