Xem ảnh

Điện thoại của Vasya chứa $n$ tấm ảnh, được đánh số từ $1$ đến $n$ và xếp thành một vòng tròn. Ban đầu ảnh số $1$ đang được mở.

Từ ảnh đang mở, Vasya có thể vuốt sang trái hoặc sang phải để chuyển sang ảnh kề, mỗi lần vuốt tốn $a$ giây. Các ảnh xếp vòng tròn: vuốt sang trái từ ảnh $1$ sẽ đến ảnh $n$, vuốt sang phải từ ảnh $n$ sẽ đến ảnh $1$.

Mỗi tấm ảnh có một hướng hiển thị: ngang hoặc dọc. Điện thoại luôn ở hướng dọc và không xoay được, nên với mỗi ảnh cần hiển thị theo hướng ngang, Vasya phải mất $b$ giây để xoay ảnh đó trước khi xem.

Vasya có $T$ giây và muốn xem được càng nhiều ảnh càng tốt. Quy tắc như sau:

• Khi mở một ảnh lần đầu tiên, Vasya mất $1$ giây để xem ảnh đó. Nếu ảnh cần hiển thị theo hướng ngang, anh mất thêm $b$ giây để xoay ảnh trước khi xem.
• Nếu ảnh đã được xem rồi thì khi đi qua lần nữa Vasya bỏ qua ngay, không tốn thêm thời gian xem hay xoay.
• Không được phép bỏ qua một ảnh chưa xem: mỗi khi chuyển đến một ảnh chưa từng xem, Vasya bắt buộc phải xem (và xoay nếu cần) ảnh đó.

Hãy tìm số lượng ảnh nhiều nhất mà Vasya có thể xem trong $T$ giây.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $a$, $b$, $T$: số lượng ảnh, thời gian vuốt sang ảnh kề, thời gian xoay một ảnh, và tổng thời gian Vasya có.
• Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các ký tự w và h. Nếu $s_i$ là w thì ảnh thứ $i$ cần hiển thị theo hướng ngang (phải xoay), nếu $s_i$ là h thì ảnh thứ $i$ hiển thị theo hướng dọc (không cần xoay).

Dữ liệu ra

Một số nguyên duy nhất: số ảnh nhiều nhất Vasya có thể xem.

Ràng buộc

• $1\le n\le 5·{10}^5$
• $1\le a,b\le 1000$
• $1\le T\le {10}^9$
• $s$ chỉ gồm các ký tự w và h

Ví dụ