查内克先生的城市可以用一架飞机来表示。他想在城里建造一个住宅区。
平面上有一些电线杆,用大小为 $$$(n + 1) \times (m + 1)$$$ 的网格 $$$a$$$ 表示。如果 $$$a_{x, y} = 1$$$,则 $$$(x, y)$$$ 处有一根电线杆。
对于每个点 $$$(x, y)$$$,将 $$$S(x, y)$$$ 定义为最近极点与 $$$(x, y)$$$ 之间的欧几里德距离的平方。形式上,两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的欧几里得距离的平方为 $$$(x_2 - x_1)^2 + (y_2 - y_1)^2$$$。
为了优化建筑计划,项目主管会要求您计算每个 $$$0 \leq x \leq n$$$ 和 $$$0 \leq y \leq m$$$ 的所有 $$$S(x, y)$$$ 的总和。帮助他找到 $$$\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$$$ 的值。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$0 \leq n, m < 2000$$$) — 网格的大小。
接下来是 $$$(n + 1)$$$ 行,每行包含 $$$(m + 1)$$$ 整数 $$$a_{i, j}$$$ ($$$0 \leq a_{i, j} \leq 1$$$) — 表示平面中电线杆位置的网格。给定网格中至少有一根电线杆。
输出
输出一个整数,表示 $$$\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$$$ 的值。
示例
输入 #1
2 2 101 000 000
输出 #1
18
输入 #2
5 4 10010 00000 01000 00001 00100 00010
输出 #2
36
注意
在第一个示例中,点 $$$(0,0)$$$、$$$(1,0)$$$、$$$(2,0)$$$、$$$(0,1)$$$、$$$(1,1)$$$ 和 $$$(2,1)$$$ 的最近电线杆位于 $$$(0, 0)$$$。而 $$$(0, 2)$$$、$$$(1,2)$$$ 和 $$$(2,2)$$$ 点的最近电线杆位于 $$$(0, 2)$$$。因此,$$$\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}} = (0 + 1 + 4) + (1 + 2 + 5) + (0 + 1 + 4) = 18$$$。