题目描述

贝茜正在通过在包含丘陵的路径上跑步来为下一场比赛训练，以便应对各种地形。她规划了一条笔直的路径，并希望尽可能跑得远，但必须在 M 秒内（1 ≤ M ≤ 10,000,000） 返回农场。

这条路径总长为 T 个单位（1 ≤ T ≤ 100,000），由等长的上坡、平地或下坡路段组成。输入数据中，第 i 段路径用字符 S_i 表示：u 为上坡，f 为平地，d 为下坡。

贝茜跑 1 个单位的上坡路需 U 秒（1 ≤ U ≤ 100），平路需 F 秒（1 ≤ F ≤ 100），下坡路需 D 秒（1 ≤ D ≤ 100）。注意：返回时，上坡路变为下坡路，下坡路变为上坡路，平地不变。

请计算贝茜能到达离农场的最远距离（单位数），且能在规定时间内返回。

输入格式

• 第 1 行：5 个空格分隔的整数 M, T, U, F, D
• 第 2 行至第 T+1 行：每行一个字符 S_i，表示第 i 段路径的类型

输出格式

• 第 1 行：一个整数，表示贝茜能到达的最远距离（单位数）。

输入输出样例

输入数据 1

13 5 3 2 1  
u  
f  
u  
d  
f  

输出数据 1

3  

题目来源

USACO 2008 年 2 月青铜组