7

- /

8 1 1

* + - *

4 5 2 6 5

Hình trên là một bảng tam giác các số nguyên không âm và các phép toán. Hãy viết chương trình để tính giá trị lớn nhất của biểu thức, đi từ đỉnh tam giác và kết thúc tại một điểm nào đó ở đáy tam giác.

Mỗi nước đi ta được quyền đi thẳng xuống ô phía dưới hoặc ô bên phải của ô ngay dưới nó (mỗi lần chỉ đi đến một ô).

Input:

+ Dòng 1: ghi số N là số lượng dòng của tam giác.

+ Các dòng tiếp theo :

* Hàng i chẵn ghi số (0<= ai < 10) , hàng i lẻ ghi phép toán (0 <= i < n) (như ví dụ)

OutPut:

+ Dòng 1: đường đi sao cho giá trị biểu thức tìm được là lớn nhất. (Dữ liệu đầu vào đảm bảo chỉ duy nhất 1 đường đi thỏa mãn)

+ Dòng 2: Giá trị tính được của biểu thức đó.

Ví dụ:

Input:

5

7

- /

8 1 1

* + - *

4 5 2 6 5

Output:

7/1*6

42