7

+ -

8 1 0

- + - -

4 5 2 6 5

Hình trên là một ví dụ về bảng tam giác chứa các số nguyên không âm và các phép toán cộng (+) và trừ (-). Biết rằng hàng chẵn sẽ chứa số nguyên và hàng lẻ chứa phép toán (chỉ số của hàng được tính từ 0), ví dụ:

Ta định nghĩa một bước đi như sau: tại một vị trí nào đó ta chỉ được đi thẳng xuống phía dưới hoặc bên phải ngay dưới nó (mỗi lần chỉ đi đến một ô).

Với cách đi như vậy, nếu đi từ đỉnh của tam giác và kết thúc tại 1 điểm nào đó ở đáy tam giác, ta sẽ thu được 1 biểu thức toán. Với mỗi biểu thức ta sẽ có 1 kết quả tính toán.

Yêu cầu: bạn hãy tính kết quả lớn nhất tìm được khi đi từ đỉnh tam giác và kết thúc tại 1 điểm nào đó ở dưới đáy tam giác.

Dữ liệu đầu vào đảm bảo là luôn tồn tại biểu thức có nghĩa khi đi từ đỉnh xuống đáy.

Dữ liệu input:

          + Dòng đầu tiên ghi số N là số lượng dòng của tam giác (1<=N<=10).

          + Dòng thứ i+1 (1<= i <= N) ghi i số nguyên không âm hoặc i phép toán (chứa dấu + và -) (giá trị mỗi số nguyên < 10)

(các giá trị trong cùng 1 dòng cách nhau 1 khoảng trắng)

Kết quả:  Chứa kết quả lớn nhất tìm được.

Ví dụ: