Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TREASRE - Kho báu trong hang

          Trong một lần thám hiểm hang động nọ, Aladdin tình cờ phát hiện ra một kho báu. Có N chồng rương (hòm) được xếp thành một hình tam giác đều. Trong hình ở link dưới, mỗi hình tròn tượng trưng cho một rương.

                https://mega.co.nz/#!PJ5XgSCK!K7tB9A0uJbmUk9d32r5jviW92OFbNyJ7-kRiBbxd0Mw

          Trừ rương ở đỉnh, mỗi rương sẽ nằm dưới 2 rương ở tầng trên. Nếu Aladdin lấy rương này mà không lấy cả 2 rương nằm trên nó, một hoặc cả 2 rương này sẽ rơi xuống và gây tai họa (đọc đoạn dưới). Dĩ nhiên là rương ở rìa thì chỉ có 1 rương nằm trên nó.

          Nhờ tài phép của thần đèn, Aladdin biết được trong mỗi chiếc rương sẽ có một số đồng tiền vàng hoặc một bùa phép sẽ làm Aladdin mất đi một số đồng. Cách để lấy được nhiều đồng xu nhất hiển nhiên là chỉ chọn những rương có đồng xu và bỏ hết rương bị ám. Tuy nhiên Aladdin không thể làm vậy bởi có 1 lời nguyền là nếu một chiếc rương bị rơi xuống hoặc bị lấy xuống mà không được mở ra thì cửa hang sẽ khép lại chôn vùi Aladdin vĩnh viễn. Ngay cả thần đèn cũng không giúp được. Vậy nên Aladdin phải lấy lần lượt các rương từ trên xuống sao cho không rương nào bị rơi và mở tất cả các rương mình lấy xuống. Thứ tự mở rương không quan trọng vì những rương bị ám bùa sẽ cướp mất của Aladdin một số đồng trong tổng số đồng tiền Aladdin tìm được.

          Vẫn còn tiếc hùi hụi vì ngày xưa ở trong hang thần bao nhiêu châu báu mà chỉ mang được ra mỗi chiếc đèn cũ rích nên Aladdin quyết lần này phải lấy được càng nhiều đồng xu càng tốt. Hãy giúp Aladdin !

Input

             Dòng đầu tiên là 1 số nguyên dương N – độ cao của chồng rương

             N dòng tiếp theo : dòng i chứa i số nguyên Aij (j<=i) là giá trị chiếc rương thứ j trên hàng i (từ trái sang phải).  Nếu Aij < 0 rương này sẽ làm Aladdin mất |Aij| đồng vàng

             Giới hạn :   N <= 3000

                             |Aij| <= 109

Output

        In ra một số nguyên duy nhất là tổng đồng tiền vàng lớn nhất mà Aladdin có thể giành được

Example

Input:

4

3

-5 3

-8 2 -8

3 9 -2 7 
Output:
7

Được gửi lên bởi:Alex & Friends
Ngày:2014-07-17
Thời gian chạy:0.400s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:by winterwolf94

hide comments
2014-07-25 03:30:35 ...
Mọi người cho em hỏi nếu tất cả là âm hết thì kết quả ra 0 phải k ạ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.