یک جدول $n\times n$ داریم که در هر خانه‌ی آن یک عدد صحیح بین -۱۰۰ و ۱۰۰ نوشته‌ایم. می‌خواهیم با شروع از $(1,1)$ (خانه‌ی سمت چپ) برسیم به $(n,n)$ (خانه‌ی پایین سمت راست). در یک حرکت می‌توانیم از یک خانه به خانه‌ی سمت راستیش و یا خانه‌ی زیریش برویم. در ضمن، اگر در ستون سمت راستی باشیم، می‌توانیم باز هم «راست» برویم و در پایان حرکت در همان سطر ولی ستون اول خواهیم بود. این شرط هم برقرار است که نمی‌توانیم وارد یک خانه بشویم که قبلا آن‌جا رفته باشیم(حتی خانه‌ی اولیه).

وزن مسیر بابر است با مجموع مقادیر خانه‌های روی مسیر. خانه‌هایی $(1,1)$ و $(n,n)$ هم در وزن محسوب می‌شوند. هدف این است که یک مسیر با شرایط فوق، با وزن ماکسیمم پیدا کنید.

در سطر اول فایل ورودی عدد $n$‌ آمده است. سپس در $n$‌ سطر عددهای جدول نوشته شده‌اند.( $n$‌ از ۳۰۰ بیش‌تر نیست)

در فایل خروجی وزن ماکسیمم را بنویسید. سپس $k$، تعداد خانه‌ها در مسیر، را بنویسید. توجه کنید که خانه‌های اول و آخر ($(1,1)$ و $(n,n)$) هم محسوب می‌شوند. سپس مختصات این $k$‌تا خانه را بنویسید، بدین صورت که برای یک خانه، اول شماره‌ی سطر و سپس شماره‌ی ستون آن را بنویسید.

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

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