為了能在下一次跑步比賽中有好的發(fā)揮，貝茜在一條山路上開始了她的訓練。貝茜希望能在每次訓練中跑得盡可能遠，不過她也知道農(nóng)場中的一條規(guī)定：奶牛獨自進山的時間不得超過M秒(1 < = M < = 10,000,000)。

整條山路被貝茜劃分成T個長度相同的小段(1 < = T < = 100,000)，并且，貝茜用S_i表示第i個小段的路況。S_i為u，f，d這3個字母之一，它們分別表示第i個小段是上坡，平地，或是下坡。

貝茜要花U秒(1 < = U < = 100)才能跑完一段上坡路，跑完一段平地的耗時是F秒(1 < = F < = 100)，跑完一段下坡路要花D秒(1 < = D < = 100)。注意，沿山路原路返回的時候，原本是上坡路的路段變成了下坡路，原本是下坡路的路段變成了上坡路。

貝茜想知道，在能按時返回農(nóng)場的前提下，她最多能在這條山路上跑多遠。

第1行：5個用空格隔開的整數(shù)：M，T，U，F(xiàn)，以及D。

第2..T+1行：第i+1行為1個字母S_i，描述了第i段山路的路況。

13 5 3 2 1
u
f
u
d
f

3