The Universe of Cup は Little Cyan Fish が暮らす場所です。この宇宙で最大の惑星である Rainbow-Earth では、あらゆるものが $1$ から $k$ までの番号が付けられた $k$ 種類の色のいずれかで塗られています。Little Cyan Fish は $n$ 個の品物を持っており、$i$ 番目の品物の色は $a_i$、価値は $b_i$ です。

最高経営責任者として、Little Cyan Fish は The 4th Universal Cup Finals の参加者への歓迎ギフトを準備しています。彼はカラフルな世界を愛しているため、各色からちょうど一つずつ、合計でちょうど $k$ 個の品物を選びたいと考えています。

何らかの理由で（おそらくその言葉が気に入っているからか、あるいは他に何を尋ねればよいか分からないからでしょう）、Little Cyan Fish は選択のスコアを、選ばれた品物のすべての順序なしペアの間の価値の差の絶対値の総和として定義します。形式的には、選ばれた添字の集合 $S \subseteq \{1, 2, \ldots, n\}$ が $|S| = k$ かつ $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$ を満たすとき、そのスコアは $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$ です。

あり得るスコアの最大値を求めてください。

入力

最初の行には、品物の個数と色の種類数をそれぞれ表す二つの整数 $n$ と $k$（$1 \le n \le 2 \times 10^5$、$1 \le k \le \min(n, 2000)$）が含まれます。

二番目の行には、$n$ 個の整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le k$）が含まれます。ここで $a_i$ は $i$ 番目の品物の色です。

三番目の行には、$n$ 個の整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i \le 10^9$）が含まれます。ここで $b_i$ は $i$ 番目の品物の価値です。

$1$ から $k$ までのすべての整数が配列 $a$ に少なくとも一回現れることが保証されます。

出力

あり得るスコアの最大値を表す一つの整数を一行に出力してください。

入出力例

入力 1

4 2
1 1 2 2
0 2 1 3

出力 1

3

入力 2

6 3
1 2 1 3 2 3
1 7 9 4 2 6

出力 2

14

入力 3

8 4
1 1 2 2 3 3 4 4
0 1 0 1 0 1 0 1

出力 3

4

注記

最初のサンプルテストケースでは、Little Cyan Fish は添字 $1$ と $4$ を選ぶことができ、スコアは $|0 - 3| = 3$ となります。

二番目のサンプルテストケースでは、添字 $3$、$5$、$4$ を選ぶと価値は $9$、$2$、$4$ となり、スコアは $|9 - 2| + |9 - 4| + |2 - 4| = 14$ となります。

三番目のサンプルテストケースでは、Little Cyan Fish は各色から一つずつ選んで価値を $0$、$0$、$1$、$1$ にすることができます。価値が異なる四つのペアがそれぞれ $1$ ずつ寄与するため、最大スコアは $4$ です。