SCANF.IR

current date=2026-02-03 09:19:02  start-date=

مثلثها

مثلثی از اعداد وجود دارد(مانند شکل). برنامه‌ای بنویسید که بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید. ریشه بالاترین عدد و برگ در پایین‌ترین قسمت قرار دارند و تنها مسیرهایی مدنظر است که از ریشه شروع شود، از تمام سطوح گذشته و در برگ خاتمه یابد. ورودی در سطر اول تعداد نمونه t مشخص شده است. در هر t<100 قسمت بعد در سطر ابتدایی عدد n<100 تعداد سطوح مثلث آورده شده است. در n خط دنباله‌ی آن در خط iام که بین 1 تا n است i عدد بین 0 تا 99 دریافت می‌شود. خروجی برنامه‌ی شما باید به ازای هر نمونه یک عدد شامل بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید.

ورودی نمونه

1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

خروجی نمونه

30