ბოულინგი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2005/06, DEC, BRONZE


ბოულინგის თამაშის დროს ძროხები არ იყენებენ ჩვეულებრივ ბურთებს. თითოეული მათგანი იღებს ერთ რიცხვს (დიაპაზონში 1..99) და ისე ეწყობიან, რომ ჰქმნიან სტანდარტულ საბოულიგე სამკუთხედს, როგორც ეს ქვემოთაა ნაჩვენები:

          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5
სხვა ძროხები დგებიან სამკუთხედის წვეროში და იწყებენ მოძრაობას სამკუთხედის ფუძისაკენ. ყოველ სვლაზე ძროხას შეუძლია გადავიდეს დიაგონალზე მდგომი ორი მეზობელი ძროხიდან ერთ–ერთთან და მისი შედეგი ტოლია ყველა იმ ძროხის რიცხვის ჯამისა, რომელთანაც ის საკუთარი მოძრაობის დროს მივა. ბოულინგში გამარჯვებულად ითვლება ის ძროხა, რომელიც მაქსიმალურ ქულას მოაგროვებს.
N (1<=N<=350) სტრიქონისაგან შედგენილი სამკუთხედისათვის განსაზღვრეთ უდიდესი შესაძლებელი ჯამი.

შესატანი მონაცემები: პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი – N. მომდევნო N სტრიქონიდან თითოეულში: სტრიქონი i+1 შეიცავს i ცალ რიცხვს და წარმოადგენს სამკუთხედის i–ურ სტრიქონს.

გამოსატანი მონაცემები: ერთი მთელი რიცხვი – უდიდესი შესაძლებელი ჯამი აღწერილი წესით მოძრაობისას.




მაგალითები

შესატანი მონაცემები
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 დაკოპირება
გამოსატანი მონაცემები
30 დაკოპირება

შენიშვნა

განმარტება. ვარსკვლავებით ნაჩვენებია ოპტიმალური გზა.
 
          7
         *
        3   8
       *
      8   1   0
       *
    2   7   4   4
       * 
  4       5        2       6        5