Description

为了迎接学校的一个长跑比赛，小明每天坚持晨练，为了适应各种长跑比赛场地，他在小区找到了一条能应对各种地形的跑道，这条跑道包括上坡、平地和下坡。

他把选择的跑道划分成T个单位长度，每个单位长度的跑道地形可能是上坡、平地或者下坡。输入中使用三个字母来表示每个单位长度跑道的地形情况，u表示是上坡，f表示是平地，d表示是下坡。

现在已知小明跑步的时间为M秒，每跑一个单位长度的上坡需要U秒、平地需要F秒、下坡需要D秒。

请帮小明计算一下，在M秒内最远能跑多远。以整数为单位，比如最后一单位长度跑道小明能跑一部分，但不能跑完整个单位长度跑道，则这一部分就不算。请认真分析输入输出样例。

Input Format

输入文件race.in的第一行包含五个整数，并且两两之间用空格隔开，分别为M，T，U，F和D。从2~T+1行：每行一个字母，表示这个单位的地形。

Output Format

输入文件race.out，用一个整数表示他能跑的最远距离。

10  5  3  2  1
u
f
u
d
f

4

Hint

1≤M≤10000000，1≤T≤100000，1≤U≤100，1≤F≤100，1≤D≤100

Source

模拟