题目描述

还记得夜雷那次分奖金的事嘛，大家并不如夜雷所想是完全理性，对于夜雷的方案，大家反对了三回啊三回！

大家把夜雷关进了一个 $n*m$ 迷宫里。

迷宫里有若干门，夜雷偷偷藏了 $k$ 把万能钥匙，每把钥匙能开一道门。

虚弱的夜雷只有 $p$ 点体力，每走一格需要花费 $1$ 点。

夜雷能成功逃出小黑屋嘛？

输入格式

第一行输入四个整数 $n,m,p,k$。

接下来 $n$行长度为 $m$ 的字符串，其中

• d 代表的是门 ; 夜雷的在经过门的时候需要消耗一把钥匙和一点体力
• s 代表的是开始的位置;
• e 代表的是结束的位置;
• w 代表的是墙的位置; 此处不可通行
• r 代表的是路的位置; 夜雷在经过的时候需要消耗一点体力

输出格式

如果夜雷能成功逃出，输出 YES，否则输出 NO。

6 6 7 1
wwwwww
rrrrrd
srddde
rwrrwr
rwrwwr
rrrrrr

YES

数据范围

$1 \leq n,m \leq 10;0 \leq p,k \leq 100$