codeforces 650D D. Image Preview (暴力+二分+dp)

Vasya's telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last photo you reach photo 1. It takes a seconds to swipe from photo to adjacent.

For each photo it is known which orientation is intended for it — horizontal or vertical. Phone is in the vertical orientation and can't be rotated. It takes b second to change orientation of the photo.

Vasya has T seconds to watch photos. He want to watch as many photos as possible. If Vasya opens the photo for the first time, he spends 1 second to notice all details in it. If photo is in the wrong orientation, he spends b seconds on rotating it before watching it. If Vasya has already opened the photo, he just skips it (so he doesn't spend any time for watching it or for changing its orientation). It is not allowed to skip unseen photos.

Help Vasya find the maximum number of photos he is able to watch during T seconds.

Input

The first line of the input contains 4 integers n, a, b, T (1 ≤ n ≤ 5·105, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 109) — the number of photos, time to move from a photo to adjacent, time to change orientation of a photo and time Vasya can spend for watching photo.

Second line of the input contains a string of length n containing symbols 'w' and 'h'.

If the i-th position of a string contains 'w', then the photo i should be seen in the horizontal orientation.

If the i-th position of a string contains 'h', then the photo i should be seen in vertical orientation.

Output

Output the only integer, the maximum number of photos Vasya is able to watch during those T seconds.

Examples

input

4 2 3 10
wwhw

output

input

5 2 4 13
hhwhh

output

input

5 2 4 1000
hhwhh

output

input

3 1 100 10
whw

output

Note

In the first sample test you can rotate the first photo (3 seconds), watch the first photo (1 seconds), move left (2 second), rotate fourth photo (3 seconds), watch fourth photo (1 second). The whole process takes exactly 10 seconds.

Note that in the last sample test the time is not enough even to watch the first photo, also you can't skip it.

题意：给你一个字符串,跟看这张照片花多少时间有关,s[i]==w,则需要1+b,s[i]==h需要1,滑到相邻的照片需要时间a,注意要从第一张开始看,滑到没看的照片时一定要花时间看,滑到已经看过的照片则不需要再花时间看了,由于这个我没读懂而且我一开始还认为不能网回滑,整的我想了一天一夜没想到解决办法,我想过贪心,线段树,单调等等,最后发现真正的题意直接想大哭一场啊啊啊啊啊啊啊啊啊;

思路：一开始有两个方向,向左或者向右,暴力枚举向左走了多少二分查找回来向右能走多少,再暴力枚举一开始就向右走,二分查找能想左走的,这里面最大的就是结果了;

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e+6;
int n,a,b,t,dp[N],c[N];
char s[N];
int main()
{
    scanf("%d%d%d%d",&n,&a,&b,&t);
    scanf("%s",s+1);
    if(s[1]=='w')t-=b+1;
    else t-=1;
    dp[0]=0;
    for(int i=2;i<=n;i++)
    {
        if(s[i]=='w')dp[i-1]=dp[i-2]+1+b+a;
        else dp[i-1]=dp[i-2]+1+a;
    }
    c[0]=0;
    for(int i=n;i>1;i--)
    {
        if(s[i]=='w')c[n-i+1]=1+b+c[n-i]+a;
        else c[n-i+1]=1+c[n-i]+a;
    }
    if(t<0)
    {
        cout<<"0";
        return 0;
    }
    else {
    int ans=1;
    for(int i=0;i<n;i++)
    {
       if(t>=c[i])
       {
           if(t>c[i]+i*a)
           {
               int pos=lower_bound(dp,dp+n-i,t-c[i]-i*a+1)-dp;//注意是t-c[i]-i*a+1,,不能忘了+1,后面也是;
               ans=max(ans,i+pos);
           }
           else
           {
               ans=max(ans,i+1);
           }
       }
       else break;
    }
    //cout<<ans<<"@"<<endl;
    for(int i=0;i<n;i++)
    {
        if(t>=dp[i])
        {
            if(t>dp[i]+i*a)
            {
                int pos=lower_bound(c,c+n-i,t-dp[i]-i*a+1)-c;
                ans=max(ans,i+pos);
            }
            else ans=max(ans,i+1);
        }
        else break;
    }
    printf("%d
",ans);
    return 0;
    }
}