CF1575M.Managing Telephone Poles

Mr. Chanek's city can be represented as a plane. He wants to build a housing complex in the city.

There are some telephone poles on the plane, which is represented by a grid $a$ of size $(n + 1) \times (m + 1)$. There is a telephone pole at $(x, y)$ if $a_{x, y} = 1$.

For each point $(x, y)$, define $S(x, y)$ as the square of the Euclidean distance between the nearest pole and $(x, y)$. Formally, the square of the Euclidean distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $(x_2 - x_1)^2 + (y_2 - y_1)^2$.

To optimize the building plan, the project supervisor asks you the sum of all $S(x, y)$ for each $0 \leq x \leq n$ and $0 \leq y \leq m$. Help him by finding the value of $\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$.

陈先生的城市可以被表示为一个平面。他希望在该城市中建造一个住宅区。

平面上存在若干电线杆，由一个大小为 $(n + 1) \times (m + 1)$ 的网格 $a$ 表示。若 $a_{x, y} = 1$，则点 $(x, y)$ 处有一根电线杆。

对每个点 $(x, y)$，定义 $S(x, y)$ 为该点到最近电线杆的欧几里得距离的平方。形式上，两点 $(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的欧几里得距离的平方为 $(x_2 - x_1)^2 + (y_2 - y_1)^2$。

为优化建筑方案，项目主管要求你计算所有 $S(x, y)$ 的总和，其中 $0 \leq x \leq n$ 且 $0 \leq y \leq m$。请帮他求出 $\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$ 的值。

The first line contains two integers $n$ and $m$ ($0 \leq n, m \lt 2000$) — the size of the grid.

Then $(n + 1)$ lines follow, each containing $(m + 1)$ integers $a_{i, j}$ ($0 \leq a_{i, j} \leq 1$) — the grid denoting the positions of telephone poles in the plane. There is at least one telephone pole in the given grid.

第一行包含两个整数 $n$ 和 $m$（$0 \leq n, m \lt 2000$）——表示网格的尺寸。

接下来 $(n + 1)$ 行，每行包含 $(m + 1)$ 个整数 $a_{i, j}$（$0 \leq a_{i, j} \leq 1$）——表示平面上电话杆位置的网格。给定网格中至少存在一根电话杆。

Output an integer denoting the value of $\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$.

输出一个整数，表示 $\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}}$ 的值。

In the first example, the nearest telephone pole for the points $(0,0)$, $(1,0)$, $(2,0)$, $(0,1)$, $(1,1)$, and $(2,1)$ is at $(0, 0)$. While the nearest telephone pole for the points $(0, 2)$, $(1,2)$, and $(2,2)$ is at $(0, 2)$. Thus, $\sum_{x=0}^{n} {\sum_{y=0}^{m} {S(x, y)}} = (0 + 1 + 4) + (1 + 2 + 5) + (0 + 1 + 4) = 18$.

在第一个例子中，点 $(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$。