【题目描述】

Dr.Kong准备参加冬季越野比赛。为了能在比赛中有好的发挥，他决定每天早上上班前在附近的一条山路上开始训练。他当然希望每次训练中跑得尽可能远，但他的时间有限，每天早上跑步训练的时间不得超过M秒 (1 <= M <= 10,000,000)。

             为了合理的安排跑步路程，Dr.Kong将整条山路划分成T个长度相同的小段(1 <= T <= 100,000)，并且，分别用u，f，d这3个字母之一来表示每个小段是上坡、平地，或是下坡。

             Dr.Kong要花t1秒(1 <= t1 <= 100)才能跑完一段上坡路，跑完一段平地的耗时是

t2秒(1 <= t2 <= 100)，跑完一段下坡路要花t3秒(1 <= t3 <= 100)。注意，沿山路原路返回的

时候，原本是上坡路的路段变成了下坡路，原本是下坡路的路段变成了上坡路。

             Dr.Kong想知道，在不超过M秒内返回的前提下，他最多能在这条山路上跑多远。

【输入格式】

第1行:  M  T  t1  t2  t3  (数据之间用一个空格隔开)

第2..T+1行:  每行为1个字母u或f或d，描述了相应段的山路路况（上坡、平地，或是下坡）

【输出格式】

输出1个整数，为Dr.Kong在不超时回到的前提下，最多能跑到几段。

【样例输入】

13 5 3 2 1



u



f



u



d



f

【样例输出】

3