#B4015. Reconstructing the Kingdom's Grain Totals

    ID: 11672 Type: Default 1000ms 256MiB

Reconstructing the Kingdom's Grain Totals

Reconstructing the Kingdom's Grain Totals

In the kingdom, the map is represented as an n×m grid. Each cell is a city that contains an unknown amount of grain \(A_{ij}\). However, due to a serious mistake, the recorded number at each city is not its own grain supply but the sum of grain in every city in its 8‐connected neighborhood (including itself). In other words, for each cell at row \(i\) and column \(j\), the reported number \(B_{ij}\) is

[ B_{ij} = \sum_{p=\max(1,i-1)}^{\min(n,i+1)} ; \sum_{q=\max(1,j-1)}^{\min(m,j+1)} A_{pq} ]

Your task is to determine the actual total grain in the kingdom, i.e. compute

[ T = \sum_{i=1}^{n} \sum_{j=1}^{m} A_{ij}, ]

given the erroneous results \(B_{ij}\). It is guaranteed that \(T\) (the total grain) can be uniquely determined even if the individual values \(A_{ij}\) might not be uniquely recoverable.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10), representing the number of rows and columns of the grid.

Then follow n lines, each containing m integers. The j-th integer in the i-th line is \(B_{ij}\), the mistakenly recorded grain amount for the city at row i and column j.

outputFormat

Output a single integer, which is the actual total grain \(T\) in the kingdom.

sample

2 2
4 4
4 4
4

</p>