The Universe of Cup är där Little Cyan Fish bor. På den största planeten i universumet, som kallas Rainbow-Earth, är allt målat i en av $k$ färger, numrerade från $1$ till $k$. Little Cyan Fish har $n$ föremål, och det $i$-te föremålet har färgen $a_i$ och värdet $b_i$.

Som verkställande direktör förbereder Little Cyan Fish välkomstgåvor till deltagarna i The 4th Universal Cup Finals. Han älskar en färgsprakande värld, så han vill välja exakt $k$ föremål, ett av varje färg.

Av någon anledning (kanske för att han gillar begreppet, eller helt enkelt för att han inte vet vad han annars ska fråga dig) definierar Little Cyan Fish poängen för ett urval som summan av de absoluta skillnaderna mellan värdena för varje oordnat par av valda föremål. Formellt, för en mängd valda index $S \subseteq \{1, 2, \ldots, n\}$ med $|S| = k$ och $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, är dess poäng $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Hitta den maximalt möjliga poängen.

Indata

Den första raden innehåller två heltal $n$ och $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), som anger antalet föremål respektive antalet färger.

Den andra raden innehåller $n$ heltal $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), där $a_i$ är färgen på det $i$-te föremålet.

Den tredje raden innehåller $n$ heltal $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), där $b_i$ är värdet på det $i$-te föremålet.

Det garanteras att varje heltal från $1$ till $k$ förekommer i fältet $a$ minst en gång.

Utdata

Skriv ut en enda rad som innehåller ett enda heltal, vilket anger den maximalt möjliga poängen.

Exempel

Indata 1

4 2
1 1 2 2
0 2 1 3

Utdata 1

3

Indata 2

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

Utdata 2

14

Indata 3

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

Utdata 3

4

Förklaring

I det första exempeltestfallet kan Little Cyan Fish välja indexen $1$ och $4$, vilket ger en poäng på $|0 - 3| = 3$.

I det andra exempeltestfallet ger valet av indexen $3$, $5$ och $4$ värdena $9$, $2$ och $4$, med en poäng på $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

I det tredje exempeltestfallet kan Little Cyan Fish välja värdena $0$, $0$, $1$ och $1$, ett från varje färg. De fyra paren med olika värden bidrar med $1$ vardera, så den maximala poängen är $4$.