The Universe of Cup은 Little Cyan Fish가 사는 곳입니다. 이 우주에서 가장 큰 행성인 Rainbow-Earth에서는 모든 것이 $1$부터 $k$까지 번호가 매겨진 $k$가지 색 중 하나로 칠해져 있습니다. Little Cyan Fish는 $n$개의 물건을 가지고 있으며, $i$번째 물건의 색은 $a_i$이고 가치는 $b_i$입니다.

최고 경영자로서 Little Cyan Fish는 The 4th Universal Cup Finals 참가자들을 위한 환영 선물을 준비하고 있습니다. 그는 다채로운 세상을 사랑하기 때문에, 각 색마다 하나씩 정확히 $k$개의 물건을 고르고 싶어 합니다.

어떤 이유에서인지(아마도 그 용어가 마음에 들거나, 아니면 단순히 여러분에게 달리 무엇을 물어봐야 할지 몰라서일 것입니다), Little Cyan Fish는 선택의 점수를 선택된 물건들의 모든 순서 없는 쌍 사이의 가치 차이의 절댓값의 합으로 정의합니다. 엄밀하게 말하면, 선택된 인덱스 집합 $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

참고

첫 번째 예제 테스트 케이스에서 Little Cyan Fish는 인덱스 $1$과 $4$를 선택할 수 있으며, 이때 점수는 $|0 - 3| = 3$입니다.

두 번째 예제 테스트 케이스에서 인덱스 $3$, $5$, $4$를 선택하면 가치는 $9$, $2$, $4$가 되며, 점수는 $|9 - 2| + |9 - 4| + |2 - 4| = 14$입니다.

세 번째 예제 테스트 케이스에서 Little Cyan Fish는 각 색에서 하나씩 골라 가치를 $0$, $0$, $1$, $1$로 선택할 수 있습니다. 가치가 서로 다른 네 쌍이 각각 $1$씩 기여하므로, 최대 점수는 $4$입니다.