The Universe of Cup on paikka, jossa Little Cyan Fish asuu. Maailmankaikkeuden suurimmalla planeetalla, nimeltään Rainbow-Earth, kaikki on maalattu yhdellä $k$ väristä, jotka on numeroitu väliltä $1$ ja $k$. Little Cyan Fishillä on $n$ esinettä, ja $i$:nnen esineen väri on $a_i$ ja arvo $b_i$.

Toimitusjohtajana Little Cyan Fish valmistelee tervetuliaislahjoja The 4th Universal Cup Finals -kilpailun osallistujille. Hän rakastaa värikästä maailmaa, joten hän haluaa valita täsmälleen $k$ esinettä, yhden kutakin väriä.

Jostakin syystä (ehkä siksi, että hän pitää tästä termistä, tai yksinkertaisesti siksi, ettei hän tiedä mitä muutakaan kysyisi sinulta) Little Cyan Fish määrittelee valinnan pistemäärän kaikkien valittujen esineiden järjestämättömien parien arvojen itseisarvoisten erotusten summana. Muodollisesti, valittujen indeksien joukolle $S \subseteq \{1, 2, \ldots, n\}$, jolle $|S| = k$ ja $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, sen pistemäärä on $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Etsi suurin mahdollinen pistemäärä.

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), jotka ilmaisevat esineiden lukumäärän ja värien lukumäärän tässä järjestyksessä.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), missä $a_i$ on $i$:nnen esineen väri.

Kolmas rivi sisältää $n$ kokonaislukua $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), missä $b_i$ on $i$:nnen esineen arvo.

On taattu, että jokainen kokonaisluku väliltä $1$ ja $k$ esiintyy taulukossa $a$ vähintään kerran.

Tuloste

Tulosta yksi rivi, joka sisältää yhden kokonaisluvun: suurimman mahdollisen pistemäärän.

Esimerkit

Syöte 1

4 2
1 1 2 2
0 2 1 3

Tuloste 1

3

Syöte 2

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

Tuloste 2

14

Syöte 3

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

Tuloste 3

4

Huomautus

Ensimmäisessä esimerkkitapauksessa Little Cyan Fish voi valita indeksit $1$ ja $4$, jolloin pistemääräksi saadaan $|0 - 3| = 3$.

Toisessa esimerkkitapauksessa indeksien $3$, $5$ ja $4$ valitseminen antaa arvot $9$, $2$ ja $4$, jolloin pistemäärä on $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

Kolmannessa esimerkkitapauksessa Little Cyan Fish voi valita arvot $0$, $0$, $1$ ja $1$, yhden kustakin väristä. Neljä eriarvoista paria kasvattavat kukin pistemäärää luvulla $1$, joten suurin pistemäärä on $4$.