CF650B.Image Preview

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.

瓦西娅的手机中存有 $n$ 张照片。当前手机上打开的是第 $1$ 张照片。通过在屏幕上左右滑动，可以切换到相邻的照片。若从第 $1$ 张照片向左滑动，则会跳转到第 $n$ 张照片；类似地，若从最后一张照片（即第 $n$ 张）向右滑动，则会跳转到第 $1$ 张照片。每次滑动到相邻照片耗时 $a$ 秒。

每张照片均有其预设方向——横屏或竖屏。手机本身固定为竖屏状态，且无法旋转。若照片方向与手机当前方向不一致，则需花费 $b$ 秒将其旋转至正确方向。

瓦西娅共有 $T$ 秒时间来浏览照片，他希望在该时间内尽可能多地观看照片。当瓦西娅首次打开某张照片时，他需花费 $1$ 秒仔细观察照片全部细节；若该照片方向错误（即为横屏），则还需额外花费 $b$ 秒进行旋转（旋转操作发生在观察之前）。若瓦西娅此前已打开过该照片，则直接跳过（即不再消耗任何时间用于观察或旋转）。不允许跳过尚未观看过的照片。

请帮助瓦西娅计算：在 $T$ 秒内，他最多能观看多少张照片？

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.

输入的第一行包含 4 个整数 $n$、$a$、$b$、$T$（$1 ≤ n ≤ 5·10^5$，$1 ≤ a,\,b ≤ 1000$，$1 ≤ T ≤ 10^9$）——分别表示照片数量、从一张照片移动到相邻照片所需时间、翻转一张照片方向所需时间，以及 Vasya 观看照片的总可用时间。

输入的第二行包含一个长度为 $n$ 的字符串，仅由字符 'w' 和 'h' 组成。

若该字符串的第 $i$ 个位置为 'w'，则第 $i$ 张照片需以横向（wide）方向观看；

若该字符串的第 $i$ 个位置为 'h'，则第 $i$ 张照片需以纵向（height）方向观看。

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

输出唯一的整数，即瓦西娅在 T 秒内能够观看的照片的最大数量。

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.

在第一个样例测试中，你可以旋转第一张照片（3 秒），观看第一张照片（1 秒），向左移动（2 秒），旋转第四张照片（3 秒），观看第四张照片（1 秒）。整个过程恰好耗时 10 秒。

注意，在最后一个样例测试中，时间甚至不足以观看第一张照片；此外，你也不能跳过它。