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$.