Đề bài

Bạn đang tổ chức một cuộc thi khiêu vũ quốc tế. Bạn đã có đủ tất cả những thứ sau:

• Một sàn nhảy gồm \(R\) hàng và \(C\) cột, được chia thành các ô vuông đơn vị;
• \(R \times C\) thí sinh;
• Một hệ thống chấm tự động tối tân cho cuộc thi.

Nhưng bạn vẫn còn thiếu khán giả! Bạn lo rằng cuộc thi có thể chưa đủ hấp dẫn, nên đã nghĩ ra một cách tính mức độ hấp dẫn của cuộc thi.

Mỗi thí sinh chiếm một ô vuông đơn vị trên sàn và ở nguyên tại đó cho đến khi bị loại. Một hàng xóm theo hướng la bàn của thí sinh \(x\) là một thí sinh \(y\) sao cho \(x\) và \(y\) nằm trên cùng một hàng hoặc cùng một cột, đồng thời không có thí sinh nào vẫn còn thi đấu trong các ô nằm giữa \(x\) và \(y\). Mỗi thí sinh có thể có từ \(0\) đến \(4\) hàng xóm theo hướng la bàn, tính cả hai đầu mút; số lượng này có thể giảm nếu tất cả các thí sinh khác ở một hướng trực giao nào đó đều đã bị loại.

Cuộc thi diễn ra theo từng vòng. Giữa vòng \(i\) và vòng \(i+1\), nếu một thí sinh \(d\) có ít nhất một hàng xóm theo hướng la bàn trong vòng \(i\), và trình độ của \(d\) nhỏ hơn nghiêm ngặt trình độ trung bình của tất cả các hàng xóm theo hướng la bàn của \(d\), thì \(d\) bị loại và không còn tham gia cuộc thi ở các vòng \(i+1, i+2, i+3, \ldots\)

Lưu ý rằng khi xét những lượt loại khác cũng xảy ra giữa vòng \(i\) và vòng \(i+1\), \(d\) vẫn được tính là hàng xóm của các hàng xóm theo hướng la bàn của mình. Những thí sinh không có bất kỳ hàng xóm theo hướng la bàn nào sẽ không bao giờ bị loại. Nếu sau một vòng không có thí sinh nào bị loại, cuộc thi kết thúc.

Mức độ hấp dẫn của một vòng là tổng trình độ của các thí sinh đang nhảy trong vòng đó, kể cả những thí sinh sẽ bị loại giữa vòng ấy và vòng kế tiếp. Mức độ hấp dẫn của cuộc thi là tổng mức độ hấp dẫn của tất cả các vòng.

Cho trình độ của các vũ công có mặt trên sàn ở vòng đầu tiên, hãy tính mức độ hấp dẫn của cuộc thi.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\). Tiếp theo là \(R\) dòng, mỗi dòng chứa \(C\) số nguyên. Giá trị thứ \(j\) trên dòng thứ \(i\) trong số các dòng này, \(S_{i,j}\), biểu thị trình độ của vũ công ở ô thuộc hàng thứ \(i\) và cột thứ \(j\) của sàn.

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)) và y là mức độ hấp dẫn của cuộc thi.

Ràng buộc

• \(1 \le S_{i,j} \le 10^6\) với mọi \(i\) và \(j\).

Phân nhóm

• Test Set 1 (phản hồi kết quả hiển thị): \(1 \le T \le 100\); \(1 \le R \times C \le 100\).
• Test Set 2 (phản hồi kết quả ẩn): \(10 \le T \le 100\); có đúng \(10\) bộ test thỏa \(1000 < R \times C \le 10^5\); có đúng \(T-10\) bộ test thỏa \(1 \le R \times C \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3

Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14

Giải thích ví dụ

??? "Giải thích"
    Trong bộ test mẫu số $1$, trên sàn chỉ có một thí sinh. Vì thí sinh này không có hàng xóm theo hướng la bàn, người đó nhảy trong một vòng rồi cuộc thi kết thúc. Do đó, đáp án bằng trình độ của vũ công, tức là $15$.

    Trong bộ test mẫu số $2$, mức độ hấp dẫn của vòng đầu tiên là

    $$
    1+1+1+1+2+1+1+1+1=10.
    $$

    Những thí sinh không ở tâm cũng không ở một góc có trình độ $1$, nhưng trình độ trung bình của các hàng xóm theo hướng la bàn của họ là $4/3$, lớn hơn $1$, nên họ bị loại. Sàn nhảy trong vòng thứ hai trông như sau:

    ```text
    1 . 1
    . 2 .
    1 . 1
    ```

    Đây là vòng cuối cùng. Mỗi thí sinh ở góc có hai hàng xóm theo hướng la bàn, nhưng trình độ trung bình của các hàng xóm bằng đúng trình độ của chính họ. Thí sinh ở tâm không có hàng xóm theo hướng la bàn. Mức độ hấp dẫn của vòng này là $1+1+2+1+1=6$. Vì vậy, mức độ hấp dẫn của cuộc thi là $10+6=16$.

    Trong bộ test mẫu số $3$, thí sinh có trình độ $1$ bị loại sau vòng đầu tiên, còn hai thí sinh kia tiếp tục thi đấu. Ở vòng thứ hai, hai thí sinh còn lại trở thành hàng xóm theo hướng la bàn, khiến thí sinh có trình độ $2$ bị loại. Vòng thứ ba chỉ còn một thí sinh, vì vậy đây là vòng cuối cùng. Mức độ hấp dẫn của ba vòng lần lượt là $6$, $5$ và $3$, nên mức độ hấp dẫn của cuộc thi là $14$.

Nguồn

Google Code Jam 2020, Vòng 1A, bài Square Dance.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.