+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کیانوش متقاضی عضویت در سازمان OC است. در روز دوم مصاحبه، سازمان خلاقیت او را مورد بررسی قرار داده است. روز دوم مسابقه کیانوش به یک مزرعه برده میشود. این مزرعه از بالا به شکل جدولی با $n$ سطر و $n$ ستون قابل رویت است که روی برخی از خانه‌های این جدول تعدادی بسته‌ی کاه قرار گرفته است. کیانوش باید با جابجاکردن این بسته‌های کاه بین خانه‌های جدول، شکلی خلاقانه روی زمین طراحی کند. کیانوش تصمیم گرفت که طوری بسته‌ها را جابجا کند که آن‌ها به شکل زیرمستطیلی با ابعاد دلخواه از جدول قرار بگیرند. روی هر خانه‌ی آن زیرمستطیل باید دقیقاً یک بسته کاه قرارگیرد و همچنین روی خانه‌‌های خارج از این مستطیل باید بسته‌ی کاهی نباشد. کیانوش میتواند در یک حرکت یک بسته‌ی کاه را از روی یک خانه‌ی جدول برداشته و روی خانه‌ی دیگری از آن بگذارد. او قصد دارد از این مستطیل بعنوان پس‌زمینه استفاده کند و با چوب و سنگ‌هایی که پیدا میکند علامت حق تکثیر (یا copyright) را روی آن حک کند. حال با ورودی گرفتن $n$ و موقعیت بسته‌های کاه، بگویید کیانوش حداقل چند حرکت لازم دارد تا به شکل دلخواهش برسد. تضمین میشود که در ورودی داده شده، کیانوش میتواند شکل دلخواهش را طراحی کند. # ورودی سطر اول ورودی شامل دو عدد $n$ و $m$ است که نمایانگر طول مزرعه و تعداد بسته‌های کاه است. سپس در هریک از $m$ سطر بعدی دو عدد آمده است که به ترتیب بیانگر شماره سطر و ستون یک بسته‌ی کاه است. سطر‌های جدول را از بالا به پایین و ستون‌‌های آن را از چپ به راست با اعداد ۱ تا $n$ شماره گذاری میکنیم. توجه داشته باشید که ممکن است دو بسته‌ی کاه در یک خانه از جدول باشند. $$1 \le n \le 100$$ $$1 \le m \le n^2$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر حداقل تعداد جابجایی‌های لازم در شکل داده‌شده است. # ورودی نمونه ۱ ``` 3 2 2 2 2 2 ``` # خروجی نمونه ۱ ``` 1 ``` # ورودی نمونه ۲ ``` 4 6 1 1 1 2 1 3 2 1 4 3 4 4 ``` # خروجی نمونه ۲ ``` 2 ``` در این مثال کافیست دو بسته‌ی کاه انتهایی را به ستون‌های دوم و سوم از سطر دوم انتقال دهیم بطوری که بسته‌های کاه مستطیلی با ۲ سطر و ۳ ستون در جدول تشکیل دهند.

حل سؤال در بانک سؤالات