شاهرخ، ماهرخ و گلرخ

شاهرخ، ماهرخ و گلرخ فرزندان سه قلوی آقا فرخ و از شاگردان امین تارخ هستند. هر کدام از آن‌ها روی یک خانه از جدولی $N×N$ که بر روی هر خانه‌ی آن یک عدد نوشته شده است، ایستاده‌اند و در حال رخ بازی هستند. رخ‌بازی به این صورت است که در هر مرحله، هر کدام از افراد خانه‌ی بعدی که قصد رفتن به آن را دارند به عنوان خانه‌ی مقصد انتخاب می‌کنند. به طوری‌که این خانه باید از خانه‌ی فعلی آن فرد با استفاده از حرکت رخ شطرنج قابل دسترس باشد و همچنین عدد نوشته شده روی خانه‌ی مقصد باید اکیداً بیشتر از خانه‌ی فعلی آن فرد باشد. همچنین با توجه به این که یک خانه فضای کافی برای ایستادن دو نفر را ندارد، خانه‌های مقصد این افراد باید با یکدیگر متمایز باشند. حال بعد از این‌که افراد مقصد‌های خود را با رعایت شروط گفته شده، انتخاب کردند هر کدام از آن‌ها به خانه‌های مقصد خود رفته و مرحله به پایان می‌رسد. آن‌ها آن‌قدر این کار را انجام می‌دهند تا دیگر قادر به انجام مرحله‌های دیگر نباشند. بدون توجه به نقش آقا داوود در این سوال، با گرفتن وضعیت اولیه‌ی شاهرخ، ماهرخ و گلرخ، بیشترین تعداد مرحله‌ای که این افراد می‌توانند بازی کنند را محاسبه کنید.

• سطر اول ورودی شامل یک عدد طبیعی، $2 \leq N \leq 12$، تعداد سطرها و ستون‌ها‌ی جدول، است.
• سطر‌های دوم تا $N+1$-ام ورودی هر کدام شامل $N$ عدد طبیعی هستند که $j$-امین عدد واقع در سطر $i+1$-ام ورودی، عدد واقع در سطر $i$-ام و ستون $j$-ام جدول را نشان می‌دهد. سطر‌های جدول از بالا به پایین و ستون‌های آن از چپ به راست با اعداد 1 تا $N$ شماره‌گذاری شده‌اند. اعداد داخل جدول حداکثر تا $10^9$ هستند.
• سطر $N+2$-ام ورودی شامل شش عدد طبیعی بین 1 تا $N$ است. اعداد اول و دوم به ترتیب شماره‌ی سطر و ستون اولیه شاهرخ، اعداد سوم و چهارم به ترتیب شماره‌ی سطر و ستون اولیه ماهرخ و اعداد پنجم و ششم به ترتیب شماره سطر و ستون اولیه گلرخ را نشان می‌دهند.
• تضمین می‌شود مکان اولیه‌ی هر سه نفر متمایز است.
• در ۲۰ درصد از ورودی‌ها، $2 \leq N \leq 6$، است.
• در ۴۰ درصد از ورودی‌ها، $2 \leq N \leq 8$، است.

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

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

شکل زیر نحوه‌ی حرکت در ورودی نمونه دوم را نشان می‌دهد. شاهرخ با دایره، ماهرخ با مثلث و گلرخ با مستطیل نشان داده شده‌اند.

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