Cubes

题意翻译

一个$ n \times n $ 的网格，每个格子上有$ a_{i,j} $ 个立方体，现在有无数方向向量为$ (vx,vy,0) $ 的平行光束从无穷远处射来，求能看到的立方体数 $ PS: $ 一个立方体能被看到当且仅当上面存在一个点，往向量$ (-vx,-vy,0) $ 处看去，一直到无穷远处中间没有任何立方体阻挡

题目描述

One day Petya got a set of wooden cubes as a present from his mom. Petya immediately built a whole city from these cubes. The base of the city is an $ n×n $ square, divided into unit squares. The square's sides are parallel to the coordinate axes, the square's opposite corners have coordinates $ (0,0) $ and $ (n,n) $ . On each of the unit squares Petya built a tower of wooden cubes. The side of a wooden cube also has a unit length. After that Petya went an infinitely large distance away from his masterpiece and looked at it in the direction of vector $ v=(v_{x},v_{y},0) $ . Petya wonders, how many distinct cubes are visible from this position. Help him, find this number. Each cube includes the border. We think that a cube is visible if there is a ray emanating from some point $ p $ , belonging to the cube, in the direction of vector $ -v $ , that doesn't contain any points, belonging to other cubes.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ v_{x} $ and $ v_{y} $ ( $ 1<=n<=10^{3} $ , $ |v_{x}|,|v_{y}|<=|10^{4}| $ , $ |v_{x}|+|v_{y}|>0 $ ). Next $ n $ lines contain $ n $ integers each: the $ j $ -th integer in the $ i $ -th line $ a_{ij} $ $ (0<=a_{ij}<=10^{9} $ , $ 1<=i,j<=n) $ represents the height of the cube tower that stands on the unit square with opposite corners at points $ (i-1,j-1) $ and $ (i,j) $ .

输出格式

Print a single integer — the number of visible cubes. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

5 -1 2
5 0 0 0 1
0 0 0 0 2
0 0 0 1 2
0 0 0 0 2
2 2 2 2 3

输出样例 #1

20

输入样例 #2

5 1 -2
5 0 0 0 1
0 0 0 0 2
0 0 0 1 2
0 0 0 0 2
2 2 2 2 3

输出样例 #2

15