Pranay has a lots of photos in gallery in his smartphone.Each photo is different from any other photo in his gallery. Initially he holds his phone in vertical position and opens his gallery. He can open any photo in his gallery at beginning.
To observe a photo he does the following operations as given :
-
If the phone is in horizontal position and photo was clicked in portrait mode, or if the phone is in vertical position and photo was clicked in landscape mode then he rotates his phone, and then he observe the photo.
-
If the phone is in horizontal position and photo was clicked in landscape mode, or if the phone is in vertical position and photo was clicked in portrait mode then he just observes the photo.
-
After it he swipes to the next photo.
It costs him 'a' seconds to rotate the phone and 'b' seconds to observe the photo.
Transaction in photos are as follows,
You can do only one swipe at time, you need to observe a photo in order to swipe again.
Right swipe : Takes you from ith photo to (i-1)th photo, for i = 1 it takes you to Nth photo.
Left swipe : Takes you from ith photo to (i+1)th photo, for i = N it takes you to 1st photo.
Gagan, his friend , has downloaded a virus in his phone . Due to this virus Pranay can either swipe left throughout, or right throughout.
Pranay has to go to meet Gagan after T seconds and he wants to view as many photos as possible before leaving. Tell him the maximum number of distinct photos he could watch/observe before meeting Gagan.
Input:
First line contains two integer 'N' denoting total number of photos in gallery and 't' denoting total time he has.
Second Line contains two integers 'a' and 'b' denoting the cost he has to pay to rotate the phone and cost to observe the photo respectively.
Third line contains a string of length N , consists of only two characters 'l' for landscape and 'p' portrait , denoting the position in which photo was clicked.
Output:
A single integer denoting maximum number of distinct photos he can observe.
Constraints :
1 <= N <= 1000
1 <= t <= 10^7
1 <= a , b <= 10^5
Subtask 1 : 30 points
1<= N <= 10000
10^12 <= t <= 10^17
1 <= a , b <= 10^5
Subtask 2 :
Original constraints
