#P17867. 虹色宇宙 3

虹色宇宙 3

K. 虹色宇宙 3

有 nn 件物品,第 ii 件的颜色为 aia_i,价值为 bib_i。共有 kk 种颜色,每种颜色至少出现一次。

需要恰好选择 kk 件物品,每种颜色各一件。若所选价值为 x1,…,xkx_1,\ldots,x_k,得分为 ∑1≤i<j≤k∣xi−xj∣\sum_{1\le i<j\le k}|x_i-x_j|。求最大得分。

输入格式

第一行 n,kn,k。第二行 nn 个颜色 aia_i。第三行 nn 个价值 bib_i。

1≤n≤2×1051\le n\le2\times10^5,1≤k≤min⁡(n,2000)1\le k\le\min(n,2000),1≤ai≤k1\le a_i\le k,0≤bi≤1090\le b_i\le10^9。本题只有一组数据。

输出格式

输出一个整数,即最大得分。注意使用 64 位整数。

样例 1

输入:

4 2
1 1 2 2
0 2 1 3

输出:

3

样例 2

输入:

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

输出:

14

样例 3

输入:

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

输出:

4