یک ماتریس $n\times n$ داریم که در هر خانه‌ی آن یک عدد طبیعی نوشته شده است. قصد داریم با شروع از ضلع بالایی آن، به ضلع پایینی برویم به طوری که:

• مسیر تنها از خانه‌های ماتریس استفاده کند.
• در طول مسیر حرکت رو به بالا نداشته باشیم. (تنها می‌توانیم به چپ، راست یا پایین برویم).
• مجموع خانه‌های مسیر کمینه شود.

برنامه‌ای بنویسید که مجموع خانه‌های این مسیر را بیابد.

در خط اول فایل ورودی عدد $n$ نوشته شده. در $n$ سطر بعد مقدار خانه‌های ماتریس آمده است. تمامی اعداد ورودی کم‌تر از ۳۰۰۰ هستند.

در فایل خروجی مقدار مجموع خانه‌های مسیر مورد نظر را بنویسید.