Bài toán: Di chuyển trên lưới

Trong một bài toán cổ điển trong lý thuyết đồ thị, cho một lưới các ô vuông, mỗi lần di chuyển từ ô này sang ô khác chỉ có thể di chuyển từ trên xuống dưới, hoặc từ trái sang phải. Câu hỏi là: hỏi bạn cần di chuyển ít nhất bao nhiêu lần để có thể đi qua toàn bộ các ô có chứa tài sản?

Mô tả bài toán:

Bài toán yêu cầu xác định số lần di chuyển tối thiểu để đi qua tất cả các ô có chứa tài sản trong một lưới. Di chuyển chỉ có thể theo 2 hướng: từ trên xuống dưới hoặc từ trái qua phải.

Dữ liệu đầu vào:

• Dòng đầu tiên chứa một số nguyên ~ T ~, là số lượng bộ dữ liệu cần xử lý.
• Mỗi bộ dữ liệu bao gồm 2 số nguyên ~ N ~, ~ M ~ (1 ≤ ~ N, M ~ ≤ 5) thể hiện kích thước của lưới ~ N \times M ~, tiếp theo là một ma trận ~ N \times M ~ các số nguyên, trong đó mỗi số nguyên là một số tài sản trong ô tương ứng. Một số nguyên dương thể hiện có tài sản và số 0 thể hiện không có tài sản.

Dữ liệu đầu ra:

• Đối với mỗi bộ dữ liệu, xuất ra một số nguyên là số lần di chuyển tối thiểu cần thiết để đi qua tất cả các ô có tài sản.

Ví dụ:

Input:

1
3 3
1 3 5
0 0 0
1 0 0

Output:

10

Giới hạn:

• Đối với 30% dữ liệu, ~ 1 \leq N, M \leq 5 ~, mỗi ô trong lưới có tài sản không vượt quá 5 lần.
• Đối với 50% dữ liệu, ~ 1 \leq N \leq 5, 1 \leq M \leq 100 ~, mỗi ô trong lưới có tài sản không vượt quá 100 lần.
• Đối với 50% dữ liệu còn lại, ~ 1 \leq T \leq 2 \times 10^3 ~, mỗi ô trong lưới có tài sản không vượt quá ~ 10^6 ~ lần.