该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题背景】

一天小明与小亮相约到一个风景如画的山洞里游玩，如下图。

洞里有许许多多的石头，而这些石头上都刻着许多漂亮的花纹。心血来潮的小明想送这些漂亮的石头作为礼物给小亮，但他想在小亮之前到达山洞出口，并且给小亮一个巨大的惊喜。

【问题描述】

我们将山洞抽象成一个N×M的矩阵，（1，1）为入口，（N，M）为出口。现在小明和小亮一同从入口进入，他们只能向下或向右走，山洞里也不免有一些不能通过的地方。小明每个单位可以移动X个格，小亮每个单位可以移动Y个格。小明一开始就捡石头（捡石头是瞬间完成，不耗时），而小亮就沿着最短路朝出口走去。

两人一开始站在入口处（即第1行，第1列的位置）。

Format

Input

第一行，N，M，X，Y，四个整数，意义如题目描述。 接下来N行，M个字符以及行为换行符，“.”表示可以通行；“*”表示不能通行；“#”表示这里有1块石头。

Output

一行，一个整数，表示小明在小亮之前到达山洞出口，最多能捡到多少块石头。

Samples

3 4 2 1
.#**
*.#*
**#.

3

样例解释

两人均沿着唯一一条线路走，如下图：

小明在途中捡拾了3块石头。

Limitation

30%,n<10,m<10

50%,n<100,m<100

100%,n<1000,m<1000,每个数据都有一条或以上的线路通往出口。