CF650B Image Preview

Vasya 的手机中有 $n$ 张照片。目前手机上打开的是第 $1$ 张照片。允许通过在屏幕上滑动手指向左或向右翻动相邻的照片。如果你从第一张照片向左滑动，你会到达第 $n$ 张照片。同样地，从最后一张照片向右滑动会到达第 $1$ 张。每次从一张照片滑动到相邻照片需要 $a$ 秒。 每张照片都有其适合的方向——横向或竖向。手机为竖向，且无法旋转。将照片方向调整为竖向需要 $b$ 秒。 Vasya 有 $T$ 秒来浏览照片。他想在这 $T$ 秒内尽可能多地观看照片。如果 Vasya 第一次打开该照片，他会花 $1$ 秒仔细看清所有细节。如果照片方向不对，需要花 $b$ 秒旋转后才能观看。如果他已经看过该照片，则会直接跳过（即不会再花时间观看或旋转）。不允许跳过未看过的照片。 请帮助 Vasya 求出在 $T$ 秒内他最多可以观看多少张照片。

输入的第一行包含四个整数 $n,a,b,T$（$1 \leq n \leq 5 \cdot 10^{5}$，$1 \leq a, b \leq 1000$，$1 \leq T \leq 10^9$），分别表示照片数量、从一张照片滑动到相邻照片所需时间、调整照片方向所需时间，以及 Vasya 能用于观看照片的时间。 第二行是一个长度为 $n$ 的字符串，由 'w' 和 'h' 组成。 如果第 $i$ 个字符为 'w'，则第 $i$ 张照片应为横向观看；如果为 'h'，则第 $i$ 张照片应为竖向观看。

输出 Vasya 能在 $T$ 秒内观看的最多照片数。

在第一个样例测试中，你可以旋转第一张照片（3 秒），观看第一张照片（1 秒），向左翻动（2 秒），旋转第四张照片（3 秒），观看第四张照片（1 秒）。整个过程正好花费 10 秒。 注意最后一个样例测试中，即使连第一张照片也不够时间看，也不能跳过第一张未看过的照片。 由 ChatGPT 5 翻译