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| = k$ және $\{a_i \mid i \in S\} = \{1, 2, \ldots, k\}$ шарттарын қанағаттандыратын таңдалған индекстер жиыны $S \subseteq \{1, 2, \ldots, n\}$ үшін оның ұпайы: $$\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$ болады.