გრძელი დისტანცია

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2007/08, FEB, BRONZE


ბესი ემზადება რბენაში შეჯიბრისათვის. სავარჯიშოდ მან შეარჩია ისეთი გზა, რომელიც
ყველანაირი ტიპის ლანდშაფტს შეიცავს. ბესი გარბის ამ გზაზე თავისი ფერმიდან რაც 
შეიძლება შორს, ოღონდ გაითვალისწინებელი აქვს, რომ აუცილებლად უნდა დაბრუნდეს
უკან - ფერმაში M (1 ≤ M ≤ 10,000,000) წამის განმავლობაში.
ბესის მიერ შერჩეული გზა შედგება T (1 ≤ T ≤ 100,000) სეგმენტისაგან.
ყველა სეგმენტი ერთნაირი სიგრძისაა, ხოლო ტიპის მიხედვით შეიძლება იყოს სამნაირი: აღმართი, დაღმართი და ვაკე. შემავალ მონაცემებში i-ური ნომრის მქონე სეგმენტი აღიწერება ერთადერთი S_i სიმბოლოთი - u, f, ან d, რომლებიც შესაბამისად აღნიშნავენ აღმართს, ვაკეს და დაღმართს. აღმართის გადალახვას ბესი ანდომებს U (1 ≤ U ≤ 100) წამს, ვაკე სეგმენტის
გარბენისათვის სჭირდება F (1 ≤ F ≤ 100) წამი, ხოლო დაღმართის
გადალახვისთვის - D (1 ≤ D ≤ 100) წამი. უკან დაბრუნებისას აღმართი
გადაიქცევა დაღმართად, დაღმართი - აღმართად, ხოლო ვაკე სეგმენტის ტიპი არ იცვლება. გამოთვალეთ ყველაზე გრძელი მანძილი (სეგმენტების რაოდენობა), რომელიც შეუძლია გაირბინოს ბესიმ, იმის გათვალისწინებით, რომ დროულად დაბრუნდება ფერმაში. შემავალი მონაცემების ფორმატი: * სტრიქონი 1: ჰარით გაყოფილი ხუთი მთელი რიცხვი: M, T, U, F, და D * სტრიქონები 2..T+1: (i+1)-ე სტრიქონი შეიცავს i-ური სეგმენტის ტიპს, გამოსახულს ერთადერთი S_i სიმბოლოთი. გამომავალი მონაცემების ფორმატი: * სტრიქონი 1: ერთი მთელი რიცხვი - ყველაზე გრძელი მანძილი (სეგმენტების რაოდენობა), რომელიც შეუძლია გაირბინოს ბესიმ, იმის გათვალისწინებით, რომ დროულად დაბრუნდება ფერმაში.



მაგალითები

შესატანი მონაცემები
13 5 3 2 1 u f u d f დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება

შენიშვნა

ბესის აქვს 13 წამი შინ დასაბრუნებლად (ძალზე ხანმოკლე ვარჯიშია!), ხოლო მთლიანი
გზა შედგება 5 სეგმენტისაგან. აღმართის გასარბენად ხარჯავს 3 წამს, ვაკეზე - 2 წამს
და დაღმართზე - 1 წამს. გზა ვიზუალურად ასე გამოიყურება:

 _/\_
/
ბესის შეუძლია გაირბინოს სამი სეგმენტი და დაბრუნდეს უკან 3+2+3+1+2+1 = 12
წამში, რაც ერთი წამით ნაკლებია დროის ლიმიტზე. თუკი ბესი მოინდომებს მომდევნო 
სეგმენტის გარბენასაც, მაშინ უკან დროულად დაბრუნებას ვეღარ მოასწრებს.