The Universe of Cup es donde vive Little Cyan Fish. En el planeta más grande del universo, llamado Rainbow-Earth, todo está pintado de uno de $k$ colores, numerados del $1$ al $k$. Little Cyan Fish tiene $n$ objetos, y el $i$-ésimo objeto tiene color $a_i$ y valor $b_i$.

Como director ejecutivo, Little Cyan Fish está preparando regalos de bienvenida para los concursantes de The 4th Universal Cup Finals. Él ama un mundo colorido, por lo que quiere elegir exactamente $k$ objetos, uno de cada color.

Por alguna razón (tal vez porque le gusta el término, o simplemente porque no sabe qué más preguntarte), Little Cyan Fish define la puntuación de una selección como la suma de las diferencias absolutas entre los valores de cada par no ordenado de objetos elegidos. Formalmente, para un conjunto de índices elegidos $S \subseteq \{1, 2, \ldots, n\}$ con $|S| = k$ y $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, su puntuación es $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Encuentra la máxima puntuación posible.

Entrada

La primera línea contiene dos enteros $n$ y $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), que indican el número de objetos y el número de colores, respectivamente.

La segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), donde $a_i$ es el color del $i$-ésimo objeto.

La tercera línea contiene $n$ enteros $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), donde $b_i$ es el valor del $i$-ésimo objeto.

Se garantiza que cada entero del $1$ al $k$ aparece en el arreglo $a$ al menos una vez.

Salida

Imprime una sola línea con un único entero, indicando la máxima puntuación posible.

Ejemplos

Entrada 1

4 2
1 1 2 2
0 2 1 3

Salida 1

3

Entrada 2

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

Salida 2

14

Entrada 3

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

Salida 3

4

Nota

En el primer caso de prueba de ejemplo, Little Cyan Fish puede elegir los índices $1$ y $4$, obteniendo una puntuación de $|0 - 3| = 3$.

En el segundo caso de prueba de ejemplo, elegir los índices $3$, $5$ y $4$ da los valores $9$, $2$ y $4$, con una puntuación de $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

En el tercer caso de prueba de ejemplo, Little Cyan Fish puede elegir los valores $0$, $0$, $1$ y $1$, uno de cada color. Los cuatro pares con valores diferentes contribuyen con $1$ cada uno, por lo que la puntuación máxima es $4$.