Жимс

Бяцхан сармагчин жимс цуглуулахаар явж байв. Тэрээр байгаа чулууны баруун урд, эсвэл зүүн урд чиглэлийн чулуу уруу л шилжиж чадна. Чулуу болгонд тодорхой хэмжээний жимс байх бөгөөд эцсийн шатанд сармагчиний авч чадах хамгийн их жимсний тоог ол.
Input
N: Эхний мөр нийт шилжилтийн тоо. a(i,j), 1 < = j < = i < = N Чулуу болгон дээр байгаа жимсний тоо 0 < = N, a(i,j) <= 200 Output Цуглуулж чадах хамгийн их жимсний тоо Example Input: 3 0 3 1 1 2 2 Output: 5
Бодлогын эх: Жимс

Бодолт
Эхлээд N-1 дэх мөрийг авч үзье. Тэгвэл a[n-1,i] дээр max(a[n,i],a[n,i+1]) ийг нэмье.
Дараа нь N-2 дэх мөрийг авч мөн уг үйлдлийг хийнэ. Энэ алхмыг үргэлжлүүлсээр 1 дэх мөр хүртэл хийнэ. Ингээд a[1,1] нь анхны бодлогын хариу болно.