장거리 달리기

베시(Bessie)는 어떤 지형에도 대비할 수 있도록 언덕이 포함된 길에서 달리며 다음 경주를 준비하고 있습니다. 베시는 하나의 직선 경로를 골랐고 농장에서 가능한 한 멀리까지 달려가고 싶어 하지만, $M$초 이내에 농장으로 반드시 돌아와야 합니다 ($1 \le M \le 10{,}000{,}000$).

베시가 고른 전체 경로의 길이는 $T$ 단위이며 ($1 \le T \le 100{,}000$), 길이가 같은 여러 구간으로 나뉩니다. 각 구간은 오르막, 평지, 내리막 중 하나입니다. $i$번째 구간은 하나의 문자 $S_i$로 주어지며, u는 오르막, f는 평지, d는 내리막을 뜻합니다.

베시는 오르막 한 단위를 달리는 데 $U$초 ($1 \le U \le 100$), 평지 한 단위에 $F$초 ($1 \le F \le 100$), 내리막 한 단위에 $D$초 ($1 \le D \le 100$)가 걸립니다. 농장으로 돌아올 때는 오르막이 내리막이 되고 내리막이 오르막이 됩니다(평지는 그대로 평지입니다).

베시가 $k$번째 구간의 끝까지 갔다가 돌아온다면, 갈 때는 구간 $1$부터 $k$까지 순서대로 지나고 올 때는 같은 구간들을 역순으로 지납니다. 베시가 농장에서 도달할 수 있으면서도 $M$초 이내에 돌아올 수 있는 가장 먼 거리(단위 수)를 구하세요.

• 첫째 줄: 공백으로 구분된 다섯 정수 $M$, $T$, $U$, $F$, $D$.
• 둘째 줄부터 $T+1$번째 줄까지: $i+1$번째 줄에는 $i$번째 구간을 나타내는 한 개의 문자 $S_i$가 주어집니다.

• 한 정수: 베시가 농장에서 도달할 수 있으면서 $M$초 이내에 돌아올 수 있는 가장 먼 거리(단위 수).