The Universe of Cup er þar sem Little Cyan Fish býr. Á stærstu reikistjörnu alheimsins, sem kallast Rainbow-Earth, er allt málað í einum af $k$ litum, sem eru númeraðir frá $1$ til $k$. Little Cyan Fish á $n$ hluti og $i$-ti hluturinn hefur litinn $a_i$ og gildið $b_i$.

Sem forstjóri er Little Cyan Fish að undirbúa móttökugjafir handa keppendum í The 4th Universal Cup Finals. Hann elskar litríkan heim, svo hann vill velja nákvæmlega $k$ hluti, einn af hverjum lit.

Af einhverjum ástæðum (kannski vegna þess að honum líkar hugtakið, eða einfaldlega vegna þess að hann veit ekki hvað annað hann á að spyrja þig um) skilgreinir Little Cyan Fish stigafjölda vals sem summu tölugilda mismunar á gildum hvers óraðaðs pars af völdum hlutum. Formlega, fyrir mengi valinna vísa $S \subseteq \{1, 2, \ldots, n\}$ þar sem $|S| = k$ og $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, er stigafjöldi þess $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Finndu mesta mögulega stigafjöldann.

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), sem tákna fjölda hluta og fjölda lita, í sömu röð.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), þar sem $a_i$ er litur $i$-ta hlutarins.

Þriðja línan inniheldur $n$ heiltölur $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), þar sem $b_i$ er gildi $i$-ta hlutarins.

Það er tryggt að sérhver heiltala frá $1$ til $k$ komi fyrir í fylkinu $a$ að minnsta kosti einu sinni.

Úttak

Skrifaðu út eina línu sem inniheldur eina heiltölu, sem táknar mesta mögulega stigafjöldann.

Dæmi

Inntak 1

4 2
1 1 2 2
0 2 1 3

Úttak 1

3

Inntak 2

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

Úttak 2

14

Inntak 3

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

Úttak 3

4

Athugasemd

Í fyrsta sýnidæminu getur Little Cyan Fish valið vísana $1$ og $4$, sem gefur stigafjöldann $|0 - 3| = 3$.

Í öðru sýnidæminu gefur val á vísunum $3$, $5$ og $4$ gildin $9$, $2$ og $4$, með stigafjöldann $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

Í þriðja sýnidæminu getur Little Cyan Fish valið gildin $0$, $0$, $1$ og $1$, eitt úr hverjum lit. Pörin fjögur með ólík gildi leggja hvert til $1$, þannig að mesti stigafjöldinn er $4$.