====== مسیر پر مغز ======

مثلثی از اعداد طبیعی کوچک‌تر از ۱۰۰ شامل حداکثر ۱۰۰۰ خط در اختیار داریم. هر مثلث در سطر اول خود شامل یک عدد، در سطر دوم شامل دو عدد و ... در سطر $n$ ام شامل $n$‌ عدد است. یک مسیر کامل مسیری است که از سطر اول مثلث آغاز و به یکی از اعداد سطر آخر ختم شود و در هر حرکت از عدد $j$ ام سطر $i$ ام به یکی از اعداد $j$ ام یا $j+1$ ام سطر $i+1$‌ ام برود. می‌خواهیم در این مثلث مسیر کاملی را پیدا کنیم که مجموع اعدادی که شامل می‌شود ماکزیمم باشد. 

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

در سطر اول فایل ورودی $m$، تعداد ورودی‌ها آمده است. سپس به ازای هر ورودی در یک سطر $n$ (تعداد سطر‌های مثلث) و در $n$ سطر بعدی به ترتیب سطرهای مثلث آمده‌اند.

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

به ازای هر ورودی، مجموع اعداد مسیر کامل ماکزیمم مثلث داده شده را در یک سطر بدون فاصله بین سطرها بنویسید.


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

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|2 \\ 2 \\ 1 \\ 2 3 \\ 3 \\ 4 \\ 1 5 \\ 5 2 2|4 \\ 11|

</WRAP>

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