====== مسیر در ماتریس اعداد ======

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

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

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

===== ورودی =====


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

===== خروجی =====

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


===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|4 \\ 5 3 1 4 \\ 1 1 1 10 \\ 1 9 9 9 \\ 1 8 7 6|6|

</WRAP>


  * [[سوال ۱۴|سوال بعد]]
  * [[سوال ۱۲|سوال قبل]]