The Universe of Cup er der Little Cyan Fish bor. På den største planeten i universet, kalt Rainbow-Earth, er alt malt i én av $k$ farger, nummerert fra $1$ til $k$. Little Cyan Fish har $n$ gjenstander, og den $i$-te gjenstanden har farge $a_i$ og verdi $b_i$.

Som administrerende direktør forbereder Little Cyan Fish velkomstgaver til deltakerne i The 4th Universal Cup Finals. Han elsker en fargerik verden, så han ønsker å velge nøyaktig $k$ gjenstander, én av hver farge.

Av en eller annen grunn (kanskje fordi han liker uttrykket, eller rett og slett fordi han ikke vet hva annet han skal spørre deg om) definerer Little Cyan Fish poengsummen til et utvalg som summen av de absolutte differansene mellom verdiene til hvert uordnet par av valgte gjenstander. Formelt, for en mengde valgte indekser $S \subseteq \{1, 2, \ldots, n\}$ med $|S| = k$ og $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, er poengsummen $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Finn den maksimalt mulige poengsummen.

Inndata

Den første linjen inneholder to heltall $n$ og $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), som angir henholdsvis antall gjenstander og antall farger.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), der $a_i$ er fargen på den $i$-te gjenstanden.

Den tredje linjen inneholder $n$ heltall $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), der $b_i$ er verdien til den $i$-te gjenstanden.

Det er garantert at hvert heltall fra $1$ til $k$ forekommer i tabellen $a$ minst én gang.

Utdata

Skriv ut én enkelt linje som inneholder ett enkelt heltall, som angir den maksimalt mulige poengsummen.

Eksempler

Inndata 1

4 2
1 1 2 2
0 2 1 3

Utdata 1

3

Inndata 2

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

Utdata 2

14

Inndata 3

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

Utdata 3

4

Merk

I det første eksempeltesttilfellet kan Little Cyan Fish velge indeksene $1$ og $4$, noe som gir en poengsum på $|0 - 3| = 3$.

I det andre eksempeltesttilfellet gir valg av indeksene $3$, $5$ og $4$ verdiene $9$, $2$ og $4$, med en poengsum på $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

I det tredje eksempeltesttilfellet kan Little Cyan Fish velge verdiene $0$, $0$, $1$ og $1$, én fra hver farge. De fire parene med ulike verdier bidrar med $1$ hver, så den maksimale poengsummen er $4$.