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$