베시는 산악마라톤을 위해 맹훈련 중이다.

목표는 주어진 M 시간 내에 가장 멀리 갔다가 돌아와야 한다. ( 1 <= M <= 10,000,000 ) 전체 길은 T 개의 길로 이루어져 있다( 1 <= T <= 100 000). 그리고 각 길은 오르막 , 평지 , 내리막 으로 이루어져 있다. i 번째 길은 문자 Si 로 표시하고 u , f , d 오르막(uphill) , 평지(flat) , 내리막(downhill)을 구분한다.

오르막 길을 오르는데 U (1 <= U <= 100) 초 걸리고 , 평지는 F ( 1 <= F <= 100) 초 , 내리막은 D( 1 <= D <= 100) 초 걸린다.

돌아올 때 내리막은 오르막이 되고 , 오르막은 내리막이 된다는 것에 유의한다.

주어진 시간 내에 그가 갈 수 있는 최대 길의 수를 구하는 것이 문제이다.

입력

• 5 개의 정수 M, T, U, F, 그리고 D 가 주어진다.
• 다음 T 줄에는 u,f,d 중 하나의 문자가 한 줄에 주어진다.

출력

• 주어진 시간 M 안에 갔다가 돌아올 수 있는 최대 길의 수를 출력한다.

입출력 예

입력

13 5 3 2 1
u
f
u
d
f

출력

3

출처: USACO 2008 February Bronze