Куглање
Кравите од фармата на чичко Трпе (од село Говрлево) решиле да одат на куглање. Малку познат факт е дека кравите всушност не користат топки за куглање, туку одбираат по еден цел број и се подредуваат во триаголна форма:
  7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5
Потоа, останатите крави го изминуваат триаголникот почнувајќи од врвот и движејќи се надолу на една од двете дијагонално соседни крави се додека не стигнат до последниот ред. Кравата со најголем збир од изминати броеви е победник на турнирот.
Доколку е даден триаголник со N редови, отпечатете го најголемиот можен збир кој може да се постигне доколку се почитуваат горенаведените правила.
Влез
Во првиот ред е запишан бројот на редови N (1 <= N <= 100). Во секој од следните N редови се запишани по i цели броеви Sij (0 <= Sij <= 100).
Излез
Излезот се состои од еден ред во кој треба да го отпечатите најголемиот можен збир.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 | излез 30 |
Објаснување: Изминувајќи го триаголникот, кравите можат да се движат надолу само на една од двете дијагонално соседни крави. Најголем збир може да се постигне доколку се движиме низ следните броеви: 7+3+8+7+5 = 30.