The Universe of Cup là nơi Little Cyan Fish sinh sống. Trên hành tinh lớn nhất trong vũ trụ, được gọi là Rainbow-Earth, mọi thứ đều được sơn bằng một trong $k$ màu, được đánh số từ $1$ đến $k$. Little Cyan Fish có $n$ món đồ, và món đồ thứ $i$ có màu $a_i$ cùng giá trị $b_i$.
Với tư cách là Giám đốc Điều hành, Little Cyan Fish đang chuẩn bị quà chào mừng cho các thí sinh của The 4th Universal Cup Finals. Cậu yêu thích một thế giới đầy sắc màu, vì vậy cậu muốn chọn đúng $k$ món đồ, mỗi màu một món.
Vì một lý do nào đó (có lẽ vì cậu thích thuật ngữ này, hoặc đơn giản vì cậu không biết phải hỏi bạn điều gì khác), Little Cyan Fish định nghĩa điểm số của một cách chọn là tổng các giá trị tuyệt đối của hiệu giữa giá trị của mọi cặp món đồ không thứ tự được chọn. Một cách hình thức, với một tập các chỉ số được chọn $S \subseteq \{1, 2, \ldots, n\}$ thỏa mãn $|S| = k$ và $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, điểm số của nó là $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$
Hãy tìm điểm số lớn nhất có thể.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), lần lượt biểu thị số lượng món đồ và số lượng màu sắc.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), trong đó $a_i$ là màu của món đồ thứ $i$.
Dòng thứ ba chứa $n$ số nguyên $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), trong đó $b_i$ là giá trị của món đồ thứ $i$.
Dữ liệu đảm bảo rằng mọi số nguyên từ $1$ đến $k$ đều xuất hiện trong mảng $a$ ít nhất một lần.
Dữ liệu ra
In ra một dòng duy nhất chứa một số nguyên duy nhất, biểu thị điểm số lớn nhất có thể.
Ví dụ
Dữ liệu vào 1
4 2 1 1 2 2 0 2 1 3
Dữ liệu ra 1
3
Dữ liệu vào 2
6 3 1 2 1 3 2 3 1 7 9 4 2 6
Dữ liệu ra 2
14
Dữ liệu vào 3
8 4 1 1 2 2 3 3 4 4 0 1 0 1 0 1 0 1
Dữ liệu ra 3
4
Ghi chú
Trong ví dụ đầu tiên, Little Cyan Fish có thể chọn các chỉ số $1$ và $4$, thu được điểm số là $|0 - 3| = 3$.
Trong ví dụ thứ hai, việc chọn các chỉ số $3$, $5$ và $4$ mang lại các giá trị $9$, $2$ và $4$, với điểm số là $|9 - 2| + |9 - 4| + |2 - 4| = 14$.
Trong ví dụ thứ ba, Little Cyan Fish có thể chọn các giá trị $0$, $0$, $1$ và $1$, mỗi màu một món. Bốn cặp có giá trị khác nhau mỗi cặp đóng góp $1$, do đó điểm số lớn nhất là $4$.