The Universe of Cup to miejsce, w którym mieszka Little Cyan Fish. Na największej planecie we wszechświecie, zwanej Rainbow-Earth, wszystko jest pomalowane na jeden z $k$ kolorów, ponumerowanych od $1$ do $k$. Little Cyan Fish ma $n$ przedmiotów, a $i$-ty przedmiot ma kolor $a_i$ oraz wartość $b_i$.

Jako dyrektor generalny, Little Cyan Fish przygotowuje prezenty powitalne dla uczestników The 4th Universal Cup Finals. Kocha kolorowy świat, więc chce wybrać dokładnie $k$ przedmiotów, po jednym z każdego koloru.

Z jakiegoś powodu (być może dlatego, że lubi to określenie, albo po prostu dlatego, że nie wie, o co innego mógłby cię zapytać), Little Cyan Fish definiuje wynik wyboru jako sumę wartości bezwzględnych różnic między wartościami każdej nieuporządkowanej pary wybranych przedmiotów. Formalnie, dla zbioru wybranych indeksów $S \subseteq \{1, 2, \ldots, n\}$ spełniającego $|S| = k$ oraz $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, jego wynik wynosi $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Znajdź maksymalny możliwy wynik.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), oznaczające odpowiednio liczbę przedmiotów oraz liczbę kolorów.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), gdzie $a_i$ jest kolorem $i$-tego przedmiotu.

Trzeci wiersz zawiera $n$ liczb całkowitych $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), gdzie $b_i$ jest wartością $i$-tego przedmiotu.

Gwarantuje się, że każda liczba całkowita od $1$ do $k$ występuje w tablicy $a$ co najmniej raz.

Wyjście

Wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą maksymalny możliwy wynik.

Przykład

Wejście 1

4 2
1 1 2 2
0 2 1 3

Wyjście 1

3

Wejście 2

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

Wyjście 2

14

Wejście 3

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

Wyjście 3

4

Uwagi

W pierwszym przykładowym przypadku testowym Little Cyan Fish może wybrać indeksy $1$ oraz $4$, uzyskując wynik $|0 - 3| = 3$.

W drugim przykładowym przypadku testowym wybranie indeksów $3$, $5$ oraz $4$ daje wartości $9$, $2$ oraz $4$, z wynikiem $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

W trzecim przykładowym przypadku testowym Little Cyan Fish może wybrać wartości $0$, $0$, $1$ oraz $1$, po jednej z każdego koloru. Cztery pary o różnych wartościach wnoszą po $1$ każda, więc maksymalny wynik wynosi $4$.