إن The Universe of Cup هو المكان الذي يعيش فيه Little Cyan Fish. على أكبر كوكب في الكون، المسمى Rainbow-Earth، كل شيء مطلي بواحد من $k$ ألوان، مرقمة من $1$ إلى $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$.