היקום 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$.