B. Просмотр фотографий
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В телефоне Васи есть n фотографий. На экране телефона в текущей момент открыта фотография номер 1. Можно перемещаться влево и вправо на соседнюю фотографиями с помощью одного движения пальца по экрану (пролистывания). Если после первой фотографии пролистнуть влево, откроется фотография номер n. Аналогично, если с фотографии n пролистнуть вправо, то откроется фотография номер 1. На пролистывание до соседней фотографии тратится a секунд.

Про каждую фотографию известно в какой она ориентации — горизонтальной и вертикальной она находится. Телефон находится в вертикальной ориентации и не может быть повёрнут. На смену ориентации картины тратится b секунд.

У Васи есть T секунд, чтобы посмотреть фотографии. За это время он хочет посмотреть как можно больше фотографий. Если Вася видит фотографию в первый раз, то он обязательно захочет её рассмотреть, потратив на это 1 секунду, при необходимости потратив b секунд на поворот фотографии в нужную ориентацию. Если Вася видит фотографию не в первый раз, он ее просто пролистывает (секунда на просмотр не тратится, менять ориентацию фотографии тоже не требуется). Пропускать не просмотренные фотографии не разрешается.

Помогите Васе определить максимальное количество фотографий, которые он успеет просмотреть за T секунд.

Входные данные

В первой строке входных данных следуют четыре целых положительных числа n, a, b, T (1 ≤ n ≤ 5·105, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 109) — количество фотографий, время, которое тратится на переход между соседними фотографиями, время, которое тратится на изменение ориентации фотографии и общее время, которое есть у Васи на просмотр фотографий.

Во второй строке следует строка длины n, состоящая из символов 'w' и 'h'.

Если на i-й позиции в строке стоит символ 'w', то фотографию с номером i нужно смотреть в горизонтальной ориентации.

Если на i-й позиции в строке стоит символ 'h', то фотографию с номером i нужно смотреть в вертикальной ориентации.

Выходные данные

Выведите единственное целое число — максимальное количество фотографий, которое успеет рассмотреть Вася за T секунд.

Примеры
Входные данные
4 2 3 10
wwhw
Выходные данные
2
Входные данные
5 2 4 13
hhwhh
Выходные данные
4
Входные данные
5 2 4 1000
hhwhh
Выходные данные
5
Входные данные
3 1 100 10
whw
Выходные данные
0
Примечание

В первом тесте из условия можно повернуть первую фотографию (3 секунды), просмотреть первую фотографию (1 секунда), сдвиуться влево (2 секунда), повернуть четвёртую фотографию (3 секунды), просмотреть четвёртую фотографию (1 секунда). На весь процесс уйдёт ровно 10 секунд.

Обратите внимание, в последнем тесте из условия времени не хватает даже на просмотр первой фотографии, при этом её нельзя пропустить.