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