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

2


Input

5 2 4 13
hhwhh


Output

4


Input

5 2 4 1000
hhwhh


Output

5


Input

3 1 100 10
whw


Output

0

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.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class DImagePreview {
    public static void main(String[] args) {
        QuickScanner sc = new QuickScanner();
        final int n = sc.nextInt();
        final int a = sc.nextInt();
        final int b = sc.nextInt();
        final int T = sc.nextInt();
        final boolean needRotate[] = new boolean[n];
        final String wh = sc.nextLine();
        for (int i = 0; i < n; i++) {
            needRotate[i] = wh.charAt(i) == 'w';
        }

        // Pre calculate right swiping
        int[] swipeRight = new int[n];
        swipeRight[0] = (needRotate[0] ? b : 0) + 1; // time for rotate (if needed) + time to see
        for (int i = 1; i < n; i++) {
            // time to get to left photo + time to swipe + time for rotate (if needed) + time to see
            swipeRight[i] = swipeRight[i - 1] + a + (needRotate[i] ? b : 0) + 1;
        }

        // Pre calculate left swiping
        int[] swipeLeft = new int[n];
        swipeLeft[0] = swipeRight[0]; // first photo is same as for swipeRight
        for (int i = 1; i < n; i++) {
            swipeLeft[i] = swipeLeft[i - 1] + a + (needRotate[n - i] ? b : 0) + 1;
        }

        // Number of watched photos
        int photos = 0;

        // Go right
        for (int i = 0; i < n; i++) {
            int timeRemain = T - swipeRight[i];
            if (timeRemain < 0) {
                break;
            }

            photos = Math.max(photos, i + 1);

            // Time to swipe left to first photo
            timeRemain -= i * a;

            // Binary search in left swipe
            if (timeRemain > 0) {
                int left = 0;
                int right = n;
                // Find where can we get by swiping left from first photo
                while (right - left > 1) {
                    int median = (left + right) / 2;
                    if (swipeLeft[median] - swipeLeft[0] <= timeRemain) {
                        left = median;
                    } else {
                        right = median;
                    }
                }
                // photos in right swipe + photos after left swipe, but less then all photos
                photos = Math.max(photos, Math.min(n, i + 1 + left));
            }
        }

        for (int i = 0; i < n; i++) {
            int timeRemain = T - swipeLeft[i];
            if (timeRemain < 0) {
                break;
            }

            photos = Math.max(photos, i + 1);

            timeRemain -= i * a;

            // Binary search in right swipe
            if (timeRemain > 0) {
                int left = 0;
                int right = n;
                // Find where can we get by swiping right from first photo
                while (right - left > 1) {
                    int median = (left + right) / 2;
                    if (swipeRight[median] - swipeRight[0] <= timeRemain) {
                        left = median;
                    } else {
                        right = median;
                    }
                }
                // photos in left swipe + photos after right swipe, but less then all photos
                photos = Math.max(photos, Math.min(n, i + 1 + left));
            }
        }

        System.out.println(photos);
    }

    private static class QuickScanner {
        BufferedReader myIn;
        StringTokenizer myToken;

        public QuickScanner() {
            this.myIn = new BufferedReader(new InputStreamReader(System.in));
            this.myToken = new StringTokenizer("", " \n\t");
        }

        public boolean hasNext() {
            while (!myToken.hasMoreTokens()) {
                try {
                    String s = myIn.readLine();
                    if (s == null) {
                        return false;
                    }
                    myToken = new StringTokenizer(s, " \n\t");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return true;
        }

        public String nextLine() {
            try {
                return myIn.readLine();
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }

        public String next() {
            hasNext();
            return myToken.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }
    }
}