The Universe of Cup — це місце, де живе Маленька Блакитна Рибка. На найбільшій планеті у всесвіті, яка називається Rainbow-Earth, усе пофарбовано в один із $k$ кольорів, пронумерованих від $1$ до $k$. Маленька Блакитна Рибка має $n$ предметів, і $i$-й предмет має колір $a_i$ та цінність $b_i$.

Як головний виконавчий директор, Маленька Блакитна Рибка готує вітальні подарунки для учасників The 4th Universal Cup Finals. Він любить барвистий світ, тому хоче вибрати рівно $k$ предметів, по одному кожного кольору.

З якоїсь причини (можливо, тому що йому подобається цей термін, або просто тому, що він не знає, про що ще вас запитати) Маленька Блакитна Рибка визначає рахунок вибору як суму модулів різниць між цінностями кожної невпорядкованої пари вибраних предметів. Формально, для множини вибраних індексів $S \subseteq \{1, 2, \ldots, n\}$ з $|S| = k$ та $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, її рахунок дорівнює $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Знайдіть максимально можливий рахунок.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), що позначають кількість предметів і кількість кольорів відповідно.

Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), де $a_i$ — колір $i$-го предмета.

Третій рядок містить $n$ цілих чисел $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), де $b_i$ — цінність $i$-го предмета.

Гарантується, що кожне ціле число від $1$ до $k$ зустрічається в масиві $a$ принаймні один раз.

Вихідні дані

Виведіть один рядок, що містить одне ціле число — максимально можливий рахунок.

Приклади

Вхідні дані 1

4 2
1 1 2 2
0 2 1 3

Вихідні дані 1

3

Вхідні дані 2

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

Вихідні дані 2

14

Вхідні дані 3

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

Вихідні дані 3

4

Примітка

У першому прикладі Маленька Блакитна Рибка може вибрати індекси $1$ і $4$, отримавши рахунок $|0 - 3| = 3$.

У другому прикладі вибір індексів $3$, $5$ і $4$ дає цінності $9$, $2$ і $4$ з рахунком $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

У третьому прикладі Маленька Блакитна Рибка може вибрати цінності $0$, $0$, $1$ і $1$, по одній кожного кольору. Чотири пари з різними цінностями дають внесок по $1$ кожна, тому максимальний рахунок дорівнює $4$.