测试数据来自 system/1731

作业已超过截止时间，您无法递交本题目。

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

---

【题目描述】

　　小H每天都在一条山路上花 \(M\) 秒的时间训练跑步，他希望能在每次训练中跑得尽可能远，即 \(M\) 秒之内，小H必须回到出发地。整条山路被小H划分成 \(N\) 个长度相同的小段，并且，小H用 \(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 在按规定时间时回到出发地的前提下，最多能跑到多远。

【输入输出样例】

　Input

13 5 3 2 1
u
f
u
d
f

　Output

3

【输入输出样例解释】

　　输入样例指出小H 跑步的最大耗时为 13 秒，山路一共被划成 5 段，各段路况如下图：

　　小H 跑完一段上坡路的耗时为 3 秒，平地为 2 秒，下坡路为 1 秒。所以他跑完山路的前 3 段，然后返回，总耗时为3+2+3+1+2+1=12 秒，只比他能的时限少 1 秒。如果他跑得更远，就无法按时回到出发地。

【数据限制】

　　\(100\%\) 的数据满足，\(M≤10^7\)，\(N≤10^5\)，\(1≤U,F,D≤100\)。

【来源】

　　Mr.he