← 返回题目列表

Codeforces · 650/B

B. 图像预览

中文机器翻译题面 查看原题

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秒。

请注意,在最后一个示例测试中,即使观看第一张照片,时间也不够,而且您不能跳过它。