Mô Tả Bài Toán:

Cho bảng A[][] kích thước N x M (N hàng, M cột). Bạn được phép đi xuống dưới, đi sang phải và đi xuống ô chéo dưới. Khi đi qua ô (i, j), điểm nhận được bằng A[i][j].

Hãy tìm đường đi từ ô (1, 1) tới ô (N, M) sao cho tổng điểm là nhỏ nhất.

Dữ Liệu Vào:

• Dòng đầu tiên là số lượng bộ test T (T ≤ 20).
• Mỗi test gồm số nguyên dương N và M. (N, M ≤ 100)
• N dòng tiếp theo, mỗi dòng gồm M số nguyên A[i][j] (0 ≤ A[i][j] ≤ 1000).

Dữ Liệu Ra:

• Với mỗi test, in trên một dòng là tổng giá trị đường đi nhỏ nhất.

Ví Dụ:

Dữ Liệu Vào:

1
3 3
1 2 3
4 8 2
1 5 3

Kết Quả:

8

Giải Thích:

• Giải thích test: Đường đi (1,1) --> (1,2) --> (2,3) --> (3,3).