متاسفانه به دلیل رکود اقتصادی امسال استقبال از باشگاه‌های بدنسازی آقا داوود کم شده و اسپانسرهای آن‌ها به دلیل نداشتن توجیه اقتصادی تصمیم به تعطیلی بعضی از باشگاه‌ها گرفته‌اند. اما می‌دانیم اسپانسرها آنقدرها هم مادی نیستند و هر کدام از آن‌ها تصمیم دارند دقیقاً یکی از باشگاه‌های تحت حمایت خود را تعطیل کنند. شاگردان آقا داوود با شنیدن این خبر، تصمیم گرفته‌اند به محض تعطیل شدن باشگاه‌ها، به نشانه‌ی اعتراض از یکی از باشگاه‌های غیر تعطیل به باشگاه غیر تعطیل دیگری راهپیمایی کنند. اما چون آدم‌های تنبلی هستند قصد دارند آن دو باشگاه را طوری انتخاب کنند که کمترین فاصله ممکن بین باشگاه‌های غیرتعطیل را داشته باشند. خبر راهپیمایی به گوش اسپانسرها رسیده و حال آنها تصمیم دارند طوری باشگاه‌های خود را تعطیل کنند که شاگردان آقا داوود طولانی‌ترین راهپیمایی ممکن را انجام دهند. حال شما باید میزان راهپیمایی شاگردان آقا داوود را در صورتی که اسپانسرها به صورت هوشمندانه عمل کنند، در خروجی چاپ کنید. برای سادگی کار باشگاه‌ها را به صورت نقطه‌هایی در صفحه‌ی مختصات در نظر بگیرید. با توجه به این که صحبت درباره‌ی باشگاه‌های آقا داوود در منهتن نیویورک است، منظور از فاصله بین باشگاه‌ها، فاصله منهتنی بین آن‌ها است. فاصله منهتنی دو نقطه‌ی $A=(X_a,Y_a)$ و $B=(X_b,Y_b)$ مساوی است با $|X_a-X_b|+|Y_a-Y_b|$.

• سطر اول ورودی شامل دو عدد طبیعی، $3 \leq N \leq 1392$، تعداد باشگاه‌های آقا داوود، و $1 \leq M \leq N/2$، تعداد اسپانسرها، است.
• سطرهای دوم تا $N+1$-ام ورودی شامل مکان باشگاه‌های آقا داوود به صورت نقطه‌هایی در صفحه مختصات و اسپانسر آن‌ها هستند. به طوریکه خط $i+1$-ام ورودی شامل سه عدد صحیح، $-10^6 \leq X_i, Y_i \leq 10^6$، مختصات باشگاه $i$-ام، و $1\leq C_i \leq M$، اسپانسر باشگاه $i$-ام است. $X_i$ عرض باشگاه $i$-ام و $Y_i$ طول آن در صفحه مختصات را نشان می‌دهند.
• تضمین می‌شود که در ورودی‌ها، مختصات باشگاه‌ها متمایز است و به ازای هر $1\leq i \leq M$ حداقل دو باشگاه وجود دارند که توسط اسپانسر شمارهی $i$ حمایت شوند.
• در 30 درصد از ورودی‌ها، $1 \leq N \leq 40$ است

در تنها سطر خروجی بیشترین راهپیمایی شاگردان آقا داوود در صورت تعطیلی هوشمندانه باشگاه‌ها را چاپ کنید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل