[HAOI2013]跑步训练

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file HAOI2013T1.in Output file HAOI2013T1.out

【题目描述】


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