Cho một tam giác số có n hàng. Từ đỉnh (hàng 1) đến đáy tam giác, mỗi bước chỉ được đi từ số ở hàng trên xuống một trong hai số đứng kề bên phải hay bên trái ở hàng dưới, và tính tích các số trên đường đi lại được một tích.

Yêu cầu: cho tam giác số, hãy tìm tích lớn nhất có thể đạt được trên một đường đi từ đỉnh xuống đáy.

Dữ liệu vào:

Từ file BAI4.INP có cấu trúc:

Dòng đầu: số tự nhiên N (0 < N < 101).

N dòng tiếp theo: từ dòng thứ 2 đến dòng thứ N+1, dòng thứ i có i số nguyên, mỗi số cách nhau một dấu cách (giá trị tuyệt đối không vượt quá 100).

Dữ liệu ra:

Ghi ra file BAI4.OUT một số nguyên là tích lớn nhất tìm được.

Ví dụ:

BAI4.INP
5
7
3 8
8 1 0
2 7 4 4
4 5 -2 6 5

BAI4.OUT
5880

Giải thích đường đi có tích lớn nhất: 7 3 8 7 5
7 × 3 × 8 × 7 × 5 = 5880