D. Кубики
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Петя получил на день рождения набор деревянных кубиков в подарок от своей мамы. Недолго думая, Петя построил из этих кубиков целый город.

Город в основании представляет собой квадрат размера n × n, разделенный на единичные квадратики. Стороны квадрата параллельны осям координат, противоположные углы квадрата имеют координаты (0, 0) и (n, n). На каждом из единичных квадратиков Петя построил башню из деревянных кубиков. Сторона деревянного кубика также имеет единичную длину.

После этого Петя отошел от своего творения на бесконечно большое расстояние и посмотрел на него в направлении вектора v = (vx, vy, 0). Петю интересует сколько различных кубиков видно из этого положения. Помогите ему, найдите это количество.

Каждый кубик включает в себя свою границу. Считается, что кубик видно, если существует луч, выходящий из некоторой точки p, принадлежащей кубику, в направлении вектора  - v, который не содержит точек, принадлежащих другим кубикам.

Входные данные

В первой строке записаны три целых числа n, vx и vy (1 ≤ n ≤ 103, |vx|, |vy| ≤ |104|, |vx| + |vy| > 0).

В следующих n строках записано по n целых чисел: j-ое число в i-ой строке aij (0 ≤ aij ≤ 109, 1 ≤ i, j ≤ n), обозначает высоту башни в кубиках, стоящую на единичном квадратике с противоположными углами в точках (i - 1, j - 1) и (i, j).

Выходные данные

Выведите единственное целое число — количество видимых кубиков.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
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
Выходные данные
20
Входные данные
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
Выходные данные
15