The Universe of Cup adalah tempat tinggal Little Cyan Fish. Di planet terbesar di alam semesta tersebut, yang bernama Rainbow-Earth, segala sesuatu dicat dengan salah satu dari $k$ warna, yang dinomori dari $1$ hingga $k$. Little Cyan Fish memiliki $n$ barang, dan barang ke-$i$ memiliki warna $a_i$ serta nilai $b_i$.

Sebagai Kepala Eksekutif, Little Cyan Fish sedang menyiapkan hadiah sambutan bagi para peserta The 4th Universal Cup Finals. Ia menyukai dunia yang penuh warna, sehingga ia ingin memilih tepat $k$ barang, masing-masing satu dari setiap warna.

Karena suatu alasan (mungkin karena ia menyukai istilah tersebut, atau sekadar karena ia tidak tahu lagi apa yang harus ditanyakan kepada Anda), Little Cyan Fish mendefinisikan skor dari suatu pemilihan sebagai jumlah selisih mutlak antara nilai-nilai dari setiap pasangan tak terurut barang yang dipilih. Secara formal, untuk himpunan indeks terpilih $S \subseteq \{1, 2, \ldots, n\}$ dengan $|S| = k$ dan $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$, skornya adalah $$\sum_{\substack{i,j \in S \\ i < j}} |b_i - b_j|.$$

Temukan skor maksimum yang mungkin.

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $k$ ($1 \le n \le 2 \times 10^5$, $1 \le k \le \min(n, 2000)$), masing-masing menyatakan banyaknya barang dan banyaknya warna.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$), dengan $a_i$ adalah warna dari barang ke-$i$.

Baris ketiga berisi $n$ bilangan bulat $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$), dengan $b_i$ adalah nilai dari barang ke-$i$.

Dijamin bahwa setiap bilangan bulat dari $1$ hingga $k$ muncul di dalam larik $a$ setidaknya satu kali.

Keluaran

Keluarkan satu baris yang berisi satu bilangan bulat, yang menyatakan skor maksimum yang mungkin.

Contoh

Masukan 1

4 2
1 1 2 2
0 2 1 3

Keluaran 1

3

Masukan 2

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

Keluaran 2

14

Masukan 3

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

Keluaran 3

4

Catatan

Pada kasus uji contoh pertama, Little Cyan Fish dapat memilih indeks $1$ dan $4$, yang menghasilkan skor sebesar $|0 - 3| = 3$.

Pada kasus uji contoh kedua, memilih indeks $3$, $5$, dan $4$ menghasilkan nilai $9$, $2$, dan $4$, dengan skor sebesar $|9 - 2| + |9 - 4| + |2 - 4| = 14$.

Pada kasus uji contoh ketiga, Little Cyan Fish dapat memilih nilai $0$, $0$, $1$, dan $1$, masing-masing satu dari setiap warna. Empat pasangan dengan nilai berbeda masing-masing menyumbang $1$, sehingga skor maksimumnya adalah $4$.