Trên đường từ nhà bé Khăn đỏ (trong truyện cô bé quàng khăn đ) đến nhà bà ngoại phải đi qua một khu rừng. Khu rừng hình chữ nhật được chia thành hàng cột, hàng được đánh số từ đến , cột được đánh số từ đến , ô ở hàng , cột được ký hiệu là ô . Nhà bé khăn đỏ ở ô còn nhà bà ngoại ở ô , chẳng hạn với ta có hình vẽ như sau (Nhà bé khăn đỏ ở ô màu đỏ, nhà bà ngoại ở ô màu xanh):
Trên khu rừng, có một số ô có bông hoa, một số ô không có gì và một số ô có sói hung dữ mà ta không thể đi vào đó.
Ta quy ước những ô có số là có sói, những ô có số là không có gì và những ô có số nguyên dương là có bông hoa với độ đẹp là số nguyên dương đó.
Hôm nay, bà ngoại bị ốm và mẹ sai bé khăn đỏ mang cơm cho bà. Khi đi mẹ có dặn bé khăn đỏ không được la cà, tức là từ một ô chỉ có thể đi sang ô kề cạnh phía bên phải hoặc kề cạnh phía dưới (tất nhiên là ô đó phải không có sói).
Trên đường đi, bé khăn đỏ muốn hái tặng bà một bó hoa đẹp nhất. Em hãy tính xem bó hoa đẹp nhất mà bé khăn đỏ có thể hái được là bao nhiêu và hãy giúp bé khăn đỏ hiếu thảo tìm một đường đi để hái được bó hoa như vậy nhé (Ở đây ta quy ước “độ đẹp” của bó hoa là tổng “độ đẹp” của tất cả các bông hoa của bó hoa đó).
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương cách nhau bởi một khoảng trắng;
dòng tiếp theo, dòng thứ chứa số nguyên là thông tin về các ô trên hàng thứ .
Dữ liệu ra:
Ghi ra một dòng duy nhất là “độ đẹp” của bó hoa đẹp nhất hái được (nếu không thể đến được nhà bà thì ghi ra số ) ;
Ví dụ:
Dữ liệu vào:
4 5
0 3 0 0 0
1 -1 2 5 0
1 2 -1 -1 0
-1 1 1 1 0
Dữ liệu ra:
10
Giải thích:
Những ô tô màu vàng là hành trình đi (trừ ô đầu và ô cuối)
