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 \(\gt 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 \leq m,n \leq 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 \leq G_{ij} \leq 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ụ:

Input 1:

3 3
0 6 0
5 8 7
0 9 0

Output 1

24

Input 2

5 3
1 0 7
2 0 6
3 4 5
0 3 0
9 0 20

Output 2

28