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

بدخواه، بدِ شما را میخواهد. او میداند که شما از خواندن داستان‌های جذاب ما!! لذت میبرید. از این رو بر آن شد که سوالی را بر ما تحمیل کند که نوشتن داستانی جذاب برای آن، کار سختی باشد. پس با مقدمه به سراغ سوال میرویم:

یک جدول $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