Bài 23.3. Hành Trình Robot Hút Bụi - [Độ khó: Khá]

Một công ty công nghệ đã phát triển một robot hút bụi thông minh có khả năng di chuyển theo một lộ trình xoắn ốc độc đáo để đảm bảo làm sạch mọi ngóc ngách của một căn phòng hình chữ nhật. Robot bắt đầu từ góc trên cùng bên trái (ô [0][0]) và di chuyển sang phải cho đến khi gặp tường hoặc đã làm sạch hàng đó. Sau đó, nó quay xuống, di chuyển xuống dưới, rồi sang trái, rồi lên trên, tiếp tục thu hẹp vùng làm việc vào bên trong cho đến khi toàn bộ căn phòng được làm sạch. Mỗi ô trong phòng có một lượng bụi nhất định. Robot sẽ thu gom toàn bộ bụi tại mỗi ô mà nó đi qua. Mỗi ô chỉ được robot đi qua một lần.

Nhiệm vụ của bạn là tính tổng lượng bụi mà robot thu gom được sau khi hoàn thành hành trình.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) (\(1 \le N, M \le 100\)), lần lượt là số hàng và số cột của căn phòng. \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên \(B_{i,j}\) (\(0 \le B_{i,j} \le 1000\)), biểu thị lượng bụi tại ô \((i, j)\).

OUTPUT FORMAT

Một số nguyên duy nhất là tổng lượng bụi mà robot đã thu gom.

Ví dụ:

Input:

3 3
1 2 3
8 9 4
7 6 5

Output:

45

Giải thích: Robot sẽ đi qua các ô theo thứ tự sau:

1. Sang phải: (0,0) -> (0,1) -> (0,2) (Bụi: 1 + 2 + 3 = 6)
2. Xuống dưới: (1,2) -> (2,2) (Bụi: 4 + 5 = 9. Tổng: 6+9=15)
3. Sang trái: (2,1) -> (2,0) (Bụi: 6 + 7 = 13. Tổng: 15+13=28)
4. Lên trên: (1,0) (Bụi: 8. Tổng: 28+8=36)
5. Sang phải (vào trong): (1,1) (Bụi: 9. Tổng: 36+9=45) Tổng lượng bụi thu gom được là 45.