Đồng cỏ của Farmer John được xem là một lưới \(N\times N\) gồm các ô cỏ vuông (\(1\le N\le500\)). Do đất không đồng đều, cỏ ở một số ô xanh hơn các ô khác. Mỗi ô \((i,j)\) có một mức độ xanh nguyên \(G(i,j)\) trong đoạn \(1\ldots200\).

Farmer John muốn chụp ảnh một lưới con hình chữ nhật của đồng cỏ. Ông muốn lưới con đủ xanh nhưng không xanh quá mức, nên quyết định chụp một lưới con có giá trị nhỏ nhất của \(G\) đúng bằng 100. Hãy xác định số bức ảnh khác nhau có thể chụp.

Lưới con có thể lớn bằng toàn bộ đồng cỏ hoặc nhỏ chỉ một ô. Tổng cộng có \(N^2(N+1)^2/4\) lưới con; giá trị này có thể không vừa trong số nguyên 32 bit nên có thể cần kiểu số nguyên 64 bit như long long trong C++.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên; tất cả các dòng cùng mô tả các giá trị \(G(i,j)\) của đồng cỏ \(N\times N\).

Dữ liệu ra

In số bức ảnh phân biệt Farmer John có thể chụp, tức số lưới con hình chữ nhật có mức độ xanh nhỏ nhất đúng bằng 100. Kết quả có thể cần kiểu số nguyên 64 bit.

Phân nhóm

• Các test 1-5 thỏa mãn \(N\le200\).
• Các test 6-10 không có ràng buộc bổ sung.

Ví dụ

3
57 120 87
200 100 150
2 141 135

8

Nguồn

USACO 2021 February Contest, Silver - Just Green Enough: https://usaco.org/index.php?page=viewproblem2&cpid=1112

Tác giả: Brian Dean.