时间限制：1秒　　内存限制：256M

---

【题目描述】

　　为准备下次跑步比赛，小H每天都在一条山路上刻苦训练。小H希望能在每次训练中跑得尽可能远，但规定每次训练的时间不得超过 \(M\) 秒，即M秒之内，小H必须回到出发地。

　　整条山路被小H划分成N个长度相同的小段，并用 \(S_i\) 表示第 \(i\) 个小段的路况。\(S_i\) 为 u,f,d 这 3 个字母之一，它们分别表示第 \(i\) 个小段是上坡、平地，或是下坡。

　　小H要花 \(U\) 秒才能跑完一段上坡路，跑完一段平地的耗时是 \(F\) 秒，跑完一段下坡路要花 \(D\) 秒。注意，沿山路原路返回的时候，原本是上坡路的路段变成了下坡路，原本是下坡路的路段变成了上坡路。

　　小H想知道，在能按时返回农场的前提下，他最多能在这条山路上跑多远。

【输入格式】

　　第一行包含五个用空格隔开的整数：\(M，N，U，F\)以及\(D\)；
　　接下来的 \(N\) 行: 第 \(i+1\) 行为 1 个字母 \(S_i\)，描述了第 \(i\) 段山路的路况。

【输出格式】

　　输出 1 个整数，为小H在按规定时间时回到出发地的前提下，最多能跑到多远。

【输入输出样例1】

　Input

13 5 3 2 1
u
f
u
d
f

　Output

3

【数据限制】

　　对于 \(100\%\) 的数据，\(M≤10^7\)，\(T≤10^5\)，\(1≤U,F,D≤100\)

【来源】

　　Mr.he