+ محدودیت ز مان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بدخواه، بدِ شما را میخواهد. او میداند که شما از خواندن داستان‌های جذاب ما!! لذت میبرید. از این رو بر آن شد که سوالی را بر ما تحمیل کند که نوشتن داستانی جذاب برای آن، کار سختی باشد. پس با مقدمه به سراغ سوال میرویم: یک جدول $n \times n$ داریم. در هر خانه ی آن یا عدد $0$ است یا عدد $1$. شما باید با کمترین حرکت کاری کنید که تمام خانه‌هایی که در آنها عدد $1$ نوشته‌شده‌است، یا روی قطر اصلی جدول باشند و یا زیر آن. شما در هر حرکت می‌توانید دو سطر مجاور را با هم جابه‌جا کنید. قطر اصلی:برای مثال 1 ها در این جدول $5 \times 5$ قطر اصلی را تشکیل می‌دهند: 10000 01000 00100 00010 00001 **در ورودی‌های داده شده، تضمین میشود همیشه میتوان به هدف گفته شده رسید.** # ورودی در سطر اول عدد $n$ آمده که نشان‌دهنده تعداد سطرهای جدول است. در $n$ سطر بعدی جدول آمده است. $$1 \le n \le 40$$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که نشان‌دهنده‌ی کمترین تعداد حرکت لازم برای این است که تمام یک‌ها یا روی قطر اصلی و یا زیر آن باشند. # مثال ## ورودی نمونه ۱ ``` 2 10 11 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 3 001 100 010 ``` ## خروجی نمونه ۲ ``` 2 ``` ## ورودی نمونه ۳ ``` 4 1110 1100 1100 1000 ``` ## خروجی نمونه ۳ ``` 4 ``` توضیح نمونه ۲: ابتدا سطر اول(از بالا) را با دوم و سپس سطر دوم را با سوم عوض میکنیم. شکل نهایی چنین است: ``` 100 010 001 ``` توضیح نمونه ۳: به ترتیب جابه‌جایی‌ها(سطر ها از بالا): 4 با 3، 3 با 2، 2 با 1، 3 با 2 شکل نهایی: ``` 1000 1100 1110 1100 ```