Cho một lưới mỏ vàng G là một ma trận có kích thước m*n. Mỗi ô trong trong mỏ vàng là một số nguyên biểu diễn lượng vàng tại ô đó (nếu ô nhận giá trị 0 có nghĩa là không có vàng). Tìm tổng lượng vàng lớn nhất trên lưới mà chúng ta có thể thu thập sao cho thỏa mãn các điều kiện sau đây:

- Tại mỗi ô, chúng ta có thể thu thập được toàn bộ lượng vàng tại ô đó.

- Tại một ô bất kì chúng ta có thể di chuyển: lên trên, xuống dưới, sang trái, sang phải.

- Chúng ta không thể thăm cùng một ô nhiều lần

- Không thăm ô có lượng vàng là 0.

- Chúng ta có thể bắt đầu và kết thúc việc thu thập vàng từ một ô bất kì trong mỏ (lưới) có lượng vàng >0

Input: Đầu vào bao gồm:

- Dòng 1: Chứa hai số nguyên m và n cách nhau bởi 1 dấu cách là kích thước của lưới mỏ vàng (1<=m,n<=15).

- m dòng tiếp theo chứa n số nguyên chỉ trữ lượng vàng tại mỗi ô trong mỏ vàng, mỗi số nguyên cách nhau bởi 1 dấu cách (0<=G[i][j]<=100)

Output: là số nguyên M biểu diễn tổng số lượng vàng lớn nhất trên đường đi thỏa mãn các điều kiện trên (đường đi được đánh dấu màu đỏ như ví dụ)

Ví dụ:

1 0 7

2 0 6

3 4 5

0 3 0

9 0 20