Dana jest piramida zawierająca elementy z określoną wagą (patrz rysunek). Zadanie polega na znalezieniu takiej drogi przejścia od wierzchołka do dowolnego punktu w podstawie piramidy, aby suma wag elementów była jak największa. Na drodze powinny się pojawić elementy z kolejnych poziomów piramidy (po 1 z każdego poziomu), wszystkie wybrane elementy powinny ze sobą sąsiadować.

Dane:
Piramida składająca się z N wierszy; i-ty wiersz składa się z i elementów; element o numerze k sąsiaduje z elementami o numerach k oraz k+1 z wiersza poniżej

Problem:
Wybrać po jednym elemencie z każdego wiersza tak, aby elementy znajdujące się w sąsiednich wierszach sąsiadowały ze sobą i suma wszystkich wybranych elementów była możliwie największa.

Rozwiązanie:
Program powinien wczytać liczbę elementów piramidy, a następnie kolejno wszystkie elementy. Jako wynik program powinien wydrukować na ekran sumę wag elementów występujących na znalezionej ścieżce. Format wejścia poniżej na przykładzie.

7 -> 3 -> 8 -> 12

10
7 3 8 8 1 0 7 12 10 10

30