Кравите од фармата на чичко Трпе (од село Говрлево) решиле да одат на куглање. Малку познат факт е дека кравите всушност не користат топки за куглање, туку одбираат по еден цел број и се подредуваат во триаголна форма:

                                             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.