The Universe of Cup est l'endroit où vit Little Cyan Fish. Sur la plus grande planète de l'univers, appelée Rainbow-Earth, tout est peint dans l'une des $k$ couleurs, numérotées de $1$ à $k$. Little Cyan Fish possède $n$ objets, et le $i$-ème objet a la couleur $a_i$ et la valeur $b_i$.
En tant que directeur général, Little Cyan Fish prépare des cadeaux de bienvenue pour les participants de The 4th Universal Cup Finals. Il aime un monde coloré, il veut donc choisir exactement $k$ objets, un de chaque couleur.
Pour une raison quelconque (peut-être parce qu'il aime ce terme, ou simplement parce qu'il ne sait pas quoi d'autre vous demander), Little Cyan Fish définit le score d'une sélection comme la somme des différences absolues entre les valeurs de chaque paire non ordonnée d'objets choisis. Formellement, pour un ensemble d'indices choisis $S \subseteq \{1, 2, \ldots, n\}$ avec $|S| = k$ et $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, son score est $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$
Trouvez le score maximal possible.
Entrée
La première ligne contient deux entiers $n$ et $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), indiquant respectivement le nombre d'objets et le nombre de couleurs.
La deuxième ligne contient $n$ entiers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), où $a_i$ est la couleur du $i$-ème objet.
La troisième ligne contient $n$ entiers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), où $b_i$ est la valeur du $i$-ème objet.
Il est garanti que chaque entier de $1$ à $k$ apparaît dans le tableau $a$ au moins une fois.
Sortie
Affichez une seule ligne contenant un seul entier, indiquant le score maximal possible.
Exemples
Entrée 1
4 2 1 1 2 2 0 2 1 3
Sortie 1
3
Entrée 2
6 3 1 2 1 3 2 3 1 7 9 4 2 6
Sortie 2
14
Entrée 3
8 4 1 1 2 2 3 3 4 4 0 1 0 1 0 1 0 1
Sortie 3
4
Remarque
Dans le premier cas de test d'exemple, Little Cyan Fish peut choisir les indices $1$ et $4$, ce qui donne un score de $|0 - 3| = 3$.
Dans le deuxième cas de test d'exemple, choisir les indices $3$, $5$ et $4$ donne les valeurs $9$, $2$ et $4$, avec un score de $|9 - 2| + |9 - 4| + |2 - 4| = 14$.
Dans le troisième cas de test d'exemple, Little Cyan Fish peut choisir les valeurs $0$, $0$, $1$ et $1$, une de chaque couleur. Les quatre paires ayant des valeurs différentes contribuent chacune pour $1$, de sorte que le score maximal est $4$.