В одном из уровней компьютерной игры вы попали в лабиринт, состоящий из n строк, каждая из которых содержит m клеток. Каждая клетка либо свободна, либо занята препятствием. Стартовая клетка находится в строке r и столбце c. За один шаг вы можете переместиться на одну клетку вверх, влево, вниз или вправо, если она не занята препятствием. Вы не можете перемещаться за границы лабиринта.
К сожалению, ваша клавиатура крайне близка к поломке, поэтому вы можете переместиться влево не более x раз и вправо не более y раз. При этом ограничений на перемещения вверх и вниз нет, поскольку клавиши, используемые для движения вверх и вниз, всё ещё в идеальном состоянии.
Теперь вы для каждой клетки поля решили установить, можно ли выбрать такую последовательность нажатий, которая приведёт вас из стартовой в эту клетку. Посчитайте, сколько клеток поля обладают таким свойством.
Выходные данные
Выведите одно число — количество клеток лабиринта, достижимых из стартовой, включая её саму.
Примечание
Клетки, достижимые в соответствующем примере, отмечены '+'.
Первый пример
+++..
+***.
+++**
*+++.
Второй пример
.++.
.+*.
.++.
.++.
| № | Входные данные | Выходные данные |
|
1
|
4 5
3 2
1 2
.....
.***.
...**
*....
|
10
|
|
2
|
4 4
2 2
0 1
....
..*.
....
....
|
7
|