問題文

正整数 $N,K$ と長さ $N$ の正整数列 $A=(A_{1},A_{2},\dots,A_{N})$ が与えられます。

$(1,2,\dots ,N)$ の順列 $P=(P_{1},P_{2},\dots ,P_{N})$ に対して以下の「問題 MST on Line 2」について考え、その答えを $f(P)$ と書きます。

問題 MST on Line 2

頂点に $1$ から $N$ までの番号がついた頂点数 $N$ の重み付き無向グラフ $G$ があります。$G$ について $1\leq i\lt j\leq N$ を満たす任意の整数の組 $(i,j)$ に対して以下が成り立ちます。

• $j-i\leq K$ ならば頂点 $i$ と頂点 $j$ の間に辺が存在して、その辺の重みは $\min(A_{P_{i}},A_{P_{j}})$
• $j-i\gt K$ ならば頂点 $i$ と頂点 $j$ の間に辺は存在しない

$G$ の最小全域木の辺の重みの和を求めてください。