题目描述

熊老师在教学之余，还经常去锻炼身体，因此他的身材非常好，八块腹肌什么的都不在话下。

熊老师每天早上都会在家旁边的一条山路上跑步，他希望每次跑步的距离尽可能远，但是熊老师太忙了，每天都有可爱的学生等着他去讲课，所以他每天早上花在跑步上的时间不能超过M秒 (1 <= M <= 10,000,000)。

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

熊老师要花t1秒(1 <= t1 <= 100)才能跑完一段上坡路，花t2秒才能跑完一段平地(1 <= t2 <= 100)，而跑完一段下坡路他需要花t3(1 <= t3 <= 100)秒。

熊老师想知道，该如何在不超过M秒内返回的前提下，最多能跑多远。

格式

输入格式

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

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

输出格式

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

样例

样例输入

13 5 3 2 1  
u  
f  
u  
d  
f

样例输出

3

限制

1s, 1024KiB for each test case.