No tag edit access

D. Cubes

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne 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.

Input

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*).

Output

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.

Examples

Input

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

Output

20

Input

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

Output

15

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/20/2017 20:14:31 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|