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.


-----Input-----

The first line of the input contains 4 integers n, a, b, T (1 ≤ n ≤ 5·10^5, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 10^9) — 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.


-----Output-----

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


-----Examples-----
Input
4 2 3 10
wwhw

Output
2

Input
5 2 4 13
hhwhh

Output
4

Input
5 2 4 1000
hhwhh

Output
5

Input
3 1 100 10
whw

Output
0



-----Note-----

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.

Difficulty: HARD
Tags: Dynamic programming

Sorting

Amortized analysis

Complete search
Skill types: Dynamic programming

Sorting

Amortized analysis

Complete search

Starter code:

Solutions:
def main():
	(n, a, b, t) = list(map(int, input().split()))
	b += 1
	l = [b if char == 'w' else 1 for char in input()]
	t -= sum(l) - a * (n + 2)
	(hi, n2) = (n, n * 2)
	n3 = n2 + 1
	lo = res = 0
	l *= 2
	while lo <= n and hi < n2:
		t -= l[hi]
		hi += 1
		while (hi - lo + (hi if hi < n3 else n3)) * a > t:
			t += l[lo]
			lo += 1
			n3 -= 1
		if res < hi - lo:
			res = hi - lo
			if res >= n:
				res = n
				break
	print(res)

def __starting_point():
	main()
__starting_point()


(n, a, b, t) = map(int, input().split())
b += 1
l = [b if char == 'w' else 1 for char in input()]
t -= sum(l) - a * (n + 2)
hi = n
n2 = n * 2
n3 = n2 + 1
lo = 0
res = 0
l *= 2
while lo <= n and hi < n2:
	t -= l[hi]
	hi += 1
	while (hi - lo + (hi if hi < n3 else n3)) * a > t or lo < hi - n:
		t += l[lo]
		lo += 1
		n3 -= 1
	if res < hi - lo:
		res = hi - lo
		if res == n:
			break
print(res)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	(n, swipe, rotate, t) = lst()
	s = input()
	ans = 0
	pre = [0] * n
	if s[0] == 'w':
		pre[0] = rotate + 1
	else:
		pre[0] = 1
	for i in range(1, n):
		pre[i] = pre[i - 1] + 1 + swipe
		if s[i] == 'w':
			pre[i] += rotate
		if pre[i] <= t:
			ans = max(ans, i + 1)
	suf = [0] * (1 + n)
	for i in range(n - 1, -1, -1):
		suf[i] = suf[i + 1] + 1 + swipe
		if s[i] == 'w':
			suf[i] += rotate
	for i in range(n):
		l = i + 1
		r = n - 1
		while l <= r:
			mid = l + r >> 1
			if pre[i] + suf[mid] + min(i, n - mid) * swipe <= t:
				r = mid - 1
			else:
				l = mid + 1
		if pre[i] + suf[l] + min(i, n - l) * swipe <= t:
			ans = max(ans, i + 1 + n - l)
	print(ans)


def main():
	(n, a, b, t) = map(int, input().split())
	b += 1
	l = [b if char == 'w' else 1 for char in input()]
	t -= sum(l) - a * (n + 2)
	(hi, n2) = (n, n * 2)
	n21 = n2 + 1
	lo = res = 0
	l *= 2
	while lo <= n and hi < n2:
		t -= l[hi]
		hi += 1
		b = hi - n
		while lo < b or (hi - lo + min(hi, n21 - lo)) * a > t:
			t += l[lo]
			lo += 1
		if res < hi - lo:
			res = hi - lo
			if res == n:
				break
	print(res)
main()


read = lambda : list(map(int, input().split()))
per = lambda L, R: R - L - 1 + min(R - n - 1, n - L)
(n, a, b, T) = read()
f = [1 + (i == 'w') * b for i in input()] * 2
(L, R) = (0, n)
ans = 0
cur = sum(f) // 2
while L <= n and R < n * 2:
	cur += f[R]
	R += 1
	while R - L > n or cur + per(L, R) * a > T:
		cur -= f[L]
		L += 1
	ans = max(ans, R - L)
print(ans)


import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n, a, b, T) = I()
s = input()
A = []
B = []
time = 0
d = {'h': 1, 'w': b + 1}
for i in range(n):
	time += d[s[i]]
	A.append(time)
	time += a
time = 0
for i in range(n - 1, 0, -1):
	time += a
	time += d[s[i]]
	B.append(time)
ans = 0
for i in range(n):
	time = A[i]
	if time > T:
		break
	l = br(B, T - time - i * a)
	ans = max(ans, i + 1 + l)
B = [A[0]] + [A[0] + i for i in B]
A = [A[i] - A[0] for i in range(1, n)]
for i in range(n):
	time = B[i]
	if time > T:
		break
	l = br(A, T - time - i * a)
	ans = max(ans, i + 1 + l)
print(min(n, ans))


def main():
	(n, a, b, t) = list(map(int, input().split()))
	a1 = a + 1
	b += a1
	(l, res) = ([b if c == 'w' else a1 for c in input()], [])
	l[0] = x = l[0] - a
	if t <= x:
		print(int(t == x))
		return
	f = res.append
	for dr in (0, 1):
		if dr:
			l[1:] = l[-1:-n:-1]
		tot = t
		for (hi, x) in enumerate(l):
			tot -= x
			if tot < 0:
				break
		else:
			print(n)
			return
		f(hi)
		tot += x
		hi -= 1
		tot -= hi * a
		lo = n
		while True:
			while lo > 0 <= tot:
				lo -= 1
				tot -= l[lo]
			f(n + hi - lo)
			if not (lo and hi):
				break
			while tot <= 0 < hi:
				tot += l[hi] + a
				hi -= 1
	print(max(res))

def __starting_point():
	main()
__starting_point()


(n, a, b, T) = map(int, input().split())
s = input()
prefsum = [0] * n
suffsum = [0] * n
for i in range(n):
	prefsum[i] = 1 if s[i] == 'h' else b + 1
	if i > 0:
		prefsum[i] += a + prefsum[i - 1]
suffsum[-1] = a
for i in range(n - 1, -1, -1):
	suffsum[i] += 1 if s[i] == 'h' else b + 1
	if i + 1 < n:
		suffsum[i] += a + suffsum[i + 1]
res = 0
l = 1
for r in range(n):
	l = max(l, r + 1)
	while l < n and suffsum[l] + r * a + prefsum[r] > T:
		l += 1
	if prefsum[r] > T:
		break
	res = max(res, r + 1 + n - l)
l = 1
for r in range(n):
	l = max(l, r + 1)
	while l < n and suffsum[l] + (n - l) * a + prefsum[r] > T:
		l += 1
	if prefsum[r] > T:
		break
	res = max(res, r + 1 + n - l)
for r in range(n):
	if prefsum[r] <= T:
		res = max(res, r + 1)
	if r > 0 and suffsum[r] + prefsum[0] <= T:
		res = max(res, n - r + 1)
print(res)


def main():
	(n, a, b, t) = map(int, input().split())
	oris = input()

	def get_time(front, rear, count_rot):
		span = front - rear
		offset = min(front, -rear)
		return (span, span * a + (span + 1) + offset * a + count_rot * b)
	front = rear = span = count_rot = new_count_rot = time = 0
	has_one = False
	for i in range(0, -n, -1):
		if oris[i] == 'w':
			new_count_rot += 1
		(new_span, new_time) = get_time(front, i, new_count_rot)
		if new_time > t:
			break
		has_one = True
		(span, time, rear, count_rot) = (new_span, new_time, i, new_count_rot)
	if not has_one:
		return 0
	maxi = max_span = n - 1
	while front < maxi and rear <= 0 and (span != max_span):
		front += 1
		if oris[front] == 'w':
			count_rot += 1
		while True:
			(new_span, time) = get_time(front, rear, count_rot)
			if time <= t:
				break
			if oris[rear] == 'w':
				count_rot -= 1
			rear += 1
			if rear > 0:
				return span + 1
		span = max(new_span, span)
	return span + 1
print(main())