The Universe of Cup è il luogo in cui vive Little Cyan Fish. Sul pianeta più grande dell'universo, chiamato Rainbow-Earth, tutto è dipinto in uno di $k$ colori, numerati da $1$ a $k$. Little Cyan Fish possiede $n$ oggetti, e l'$i$-esimo oggetto ha colore $a_i$ e valore $b_i$.
In qualità di amministratore delegato, Little Cyan Fish sta preparando dei regali di benvenuto per i concorrenti di The 4th Universal Cup Finals. Egli ama un mondo colorato, quindi vuole scegliere esattamente $k$ oggetti, uno per ciascun colore.
Per qualche motivo (forse perché gli piace il termine, o semplicemente perché non sa cos'altro chiederti), Little Cyan Fish definisce il punteggio di una selezione come la somma delle differenze assolute tra i valori di ogni coppia non ordinata di oggetti scelti. Formalmente, per un insieme di indici scelti $S \subseteq \{1, 2, \ldots, n\}$ con $|S| = k$ e $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, il suo punteggio è $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$
Trova il punteggio massimo possibile.
Input
La prima riga contiene due interi $n$ e $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), che indicano rispettivamente il numero di oggetti e il numero di colori.
La seconda riga contiene $n$ interi $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), dove $a_i$ è il colore dell'$i$-esimo oggetto.
La terza riga contiene $n$ interi $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), dove $b_i$ è il valore dell'$i$-esimo oggetto.
È garantito che ogni intero da $1$ a $k$ compaia nell'array $a$ almeno una volta.
Output
Stampa una singola riga contenente un singolo intero, che indica il punteggio massimo possibile.
Esempi
Input 1
4 2 1 1 2 2 0 2 1 3
Output 1
3
Input 2
6 3 1 2 1 3 2 3 1 7 9 4 2 6
Output 2
14
Input 3
8 4 1 1 2 2 3 3 4 4 0 1 0 1 0 1 0 1
Output 3
4
Note
Nel primo caso di prova d'esempio, Little Cyan Fish può scegliere gli indici $1$ e $4$, ottenendo un punteggio di $|0 - 3| = 3$.
Nel secondo caso di prova d'esempio, scegliere gli indici $3$, $5$ e $4$ dà i valori $9$, $2$ e $4$, con un punteggio di $|9 - 2| + |9 - 4| + |2 - 4| = 14$.
Nel terzo caso di prova d'esempio, Little Cyan Fish può scegliere i valori $0$, $0$, $1$ e $1$, uno per ciascun colore. Le quattro coppie con valori diversi contribuiscono ciascuna per $1$, quindi il punteggio massimo è $4$.