Trong một trò chơi, bản đồ đại dương được biểu diễn bằng một ô vuông có kích thước \(n \times n\). Các dòng của bảng được đánh số từ \(1\) đến \(n\), từ trên xuống dưới. Các cột của bảng được đánh số từ \(1\) đến \(n\), từ trái sang phải. Ô nằm trên giao của dòng \(i\) và cột \(j\) của bảng gọi là ô \((i,j)\)

Ô \((i,j)\) chứa một số nguyên \(r\) biểu diễn một cơn bão có bánh kính là \(r\), bão có tâm tại ô \((i,j)\); các ô \((x,y)\) sẽ bị ảnh hưởng bởi bão tại ô \((i,j)\) khi \(|x-i|+|y-j|\le r\) (khoảng cách Manhattan). Nếu \(r=0\) thì tại ô đó không có bão.

Yêu cầu:

• Đếm số lượng ô không bị ảnh hưởng bão

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) \((n \le 3000)\) mô tả kích thước của bảng;
• \(n\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên \(r\) \((0 \le r \le n)\) mô tả các cơn bão.

Output

• Một số duy nhất là số lượng ô không bị ảnh hưởng bão.

Scoring

• Substask 1 (40% số điểm): \(n \le 100\)
• Substask 2 (20% số điểm): \(r \le 20\)
• Substask 3 (20% số điểm): Các ô có bão đều có bán kính bằng nhau;
• Substask 4 (20% số điểm): Không có ràng buộc gì thêm.

Input

4
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 0

Output

5