Im Universe of Cup lebt Little Cyan Fish. Auf dem größten Planeten des Universums, genannt Rainbow-Earth, ist alles in einer von $k$ Farben gestrichen, die von $1$ bis $k$ nummeriert sind. Little Cyan Fish besitzt $n$ Gegenstände, und der $i$-te Gegenstand hat die Farbe $a_i$ und den Wert $b_i$.

Als Geschäftsführer bereitet Little Cyan Fish Willkommensgeschenke für die Teilnehmer der The 4th Universal Cup Finals vor. Er liebt eine bunte Welt, daher möchte er genau $k$ Gegenstände auswählen, einen von jeder Farbe.

Aus irgendeinem Grund (vielleicht weil ihm der Begriff gefällt, oder einfach weil er nicht weiß, was er dich sonst fragen soll) definiert Little Cyan Fish die Punktzahl einer Auswahl als die Summe der absoluten Differenzen zwischen den Werten jedes ungeordneten Paares ausgewählter Gegenstände. Formal gilt für eine Menge ausgewählter Indizes $S \subseteq \{1, 2, \ldots, n\}$ mit $|S| = k$ und $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, dass ihre Punktzahl $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$ beträgt.

Finde die maximal mögliche Punktzahl.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), die die Anzahl der Gegenstände bzw. die Anzahl der Farben angeben.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), wobei $a_i$ die Farbe des $i$-ten Gegenstands ist.

Die dritte Zeile enthält $n$ ganze Zahlen $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), wobei $b_i$ der Wert des $i$-ten Gegenstands ist.

Es wird garantiert, dass jede ganze Zahl von $1$ bis $k$ im Array $a$ mindestens einmal vorkommt.

Ausgabe

Gib eine einzige Zeile mit einer einzigen ganzen Zahl aus, die die maximal mögliche Punktzahl angibt.

Beispiele

Eingabe 1

4 2
1 1 2 2
0 2 1 3

Ausgabe 1

3

Eingabe 2

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

Ausgabe 2

14

Eingabe 3

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

Ausgabe 3

4

Hinweis

Im ersten Beispieltestfall kann Little Cyan Fish die Indizes $1$ und $4$ wählen, was eine Punktzahl von $|0 - 3| = 3$ ergibt.

Im zweiten Beispieltestfall ergibt die Wahl der Indizes $3$, $5$ und $4$ die Werte $9$, $2$ und $4$ mit einer Punktzahl von $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

Im dritten Beispieltestfall kann Little Cyan Fish die Werte $0$, $0$, $1$ und $1$ wählen, jeweils einen von jeder Farbe. Die vier Paare mit unterschiedlichen Werten tragen jeweils $1$ bei, sodass die maximale Punktzahl $4$ beträgt.