Vasya 的电话包含 n 张照片。目前,1 号照片已在手机上打开。通过在屏幕上滑动手指可以左右移动到相邻的照片。如果从第一张照片向左滑动,您将看到照片 n。同样,从最后一张照片向右滑动即可到达照片 1。从照片滑动到相邻照片需要几秒钟的时间。
对于每张照片,都知道它的方向是水平还是垂直。手机处于垂直方向,无法旋转。改变照片的方向需要 b 秒。
Vasya 有 T 秒时间观看照片。他想看尽可能多的照片。如果 Vasya 第一次打开照片,他会花 1 秒的时间注意到照片中的所有细节。如果照片方向错误,他会花 b 秒旋转它,然后再观看。如果 Vasya 已经打开了照片,他就会跳过它(这样他就不会花任何时间观看它或更改其方向)。不允许跳过未见过的照片。
帮助 Vasya 找到他在 T 秒内能够观看的最大照片数。
输入
输入的第一行包含 4 个整数 n、a、b、T (1 ≤ n ≤ 5 105, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 109) — 照片数量、从照片移动到相邻照片的时间、改变照片方向的时间以及 Vasya 观看照片的时间。
输入的第二行包含长度为 n 的字符串,其中包含符号“w”和“h”。
如果字符串的第 i 个位置包含“w”,则照片 i 应该以水平方向显示。
如果字符串的第 i 个位置包含“h”,则照片 i 应该以垂直方向显示。
输出
输出唯一的整数,即 Vasya 在这 T 秒内能够观看的最大照片数。
示例
输入 #1
4 2 3 10 wwhw
输出 #1
2
输入 #2
5 2 4 13 hhwhh
输出 #2
4
输入 #3
5 2 4 1000 hhwhh
输出 #3
5
输入#4
3 1 100 10 whw
输出#4
0
注意
在第一个示例测试中,您可以旋转第一张照片(3秒),观看第一张照片(1秒),向左移动(2秒),旋转第四张照片(3秒),观看第四张照片(1秒)。整个过程正好需要10秒。
请注意,在最后一个示例测试中,即使观看第一张照片,时间也不够,而且您不能跳过它。