問題文

ある$n$に対する$[1,2,\ldots,n]$の置換(permutation) $x$に対し、$f(x)$を辞書順で$x$の次の置換とする。 ただし、$x$が辞書順で最後のもの$[n,n-1, \ldots, 1]$である場合は、$f(x)$を辞書順で最初のもの$[1,2,\ldots,n]$として定義する。 たとえば、$f([1, 2, 3]) = [1, 3, 2]$, $f(f([3,1,2])) = f([3,2,1]) = [1,2,3]$ となる。

ある$n$に対し長さが$n$の2つの配列$x, y$に対する$L_1$距離 $\displaystyle \sum_{i=1}^n |x_i - y_i|$を${\rm dist}(x, y)$として表す。 たとえば、$x = [1,2,3], y = [3,2,1]$なら${\rm dist}(x, y) = |1-3| + |2-2| + |3-1| = 4$となる。

置換$p$が与えられたとき、置換の列$A$を、$A_0 = p$, $A_i = f(A_{i-1})$ ($i \in [1,2,\ldots]$) として定義する。 つまり、$A_i$は$p$に$f$を$i$回適用したものである。 たとえば、$p = [2,1,3]$ なら $A = [[2,1,3],[2,3,1],[3,1,2],[3,2,1],[1,2,3],\dots]$ となる。 $A$の添字は0から始まることに注意せよ。

整数$N$, 整数$K$, 長さ$N$の置換$p$, 長さ$N$の配列$B$ が入力として与えられる。 $\displaystyle \sum_{i=0}^{K-1} {\rm dist}(A_i, B)$を求めよ。

入力

$N$ $K$
$p_1$ $p_2$ $\ldots$ $p_N$
$B_1$ $B_2$ $\ldots$ $B_N$

1行目に、整数$N (1 \le N \le 10^5)$, 整数$K (0 \le K \le 10^5)$が空白区切りで与えられる。 2行目に、長さ$N$の$[1,2,\ldots,N]$の置換$p$が空白区切りで与えられる。 3行目に、長さ$N$の整数の配列$B (1 \le B_i \le 10^8)$が空白区切りで与えられる。

出力

$\displaystyle \sum_{i=0}^{K-1} {\rm dist}(A_i, B)$を1行に出力せよ。

ヒント

総和の対象が$L_1$距離であることに大きな意味はないです。

サンプル

3 5
2 1 3
3 2 1

12

3 36
1 2 3
1 1 1

108

1 100000
1
1

0

2 100000
1 2
100000000 100000000

19999999700000