B. Зураг үзэх

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Васягийн гар утас $n$ ширхэг фото зурагтай. 1 дугаартай зураг утсан дээр нээгдсэн байна. Зүүн эсвэл баруун тийш хуруугаа дэлгэцэн дээр гүйлгэснээр хөрш зурагруу шилжиж болно. Хэрвээ та эхний зургаас зүүн тийш хуруугаа гүйлгэвэл $n$ дугаартай зурагт очно. Үүнтэй ижлээр $n$ дугаартай зургаас баруун тийш хуруугаа гүйлгэвэл $1$ дугаартай зурган дээр очно. Хөрш зурагруу очихын тулд $a$ секунд зарцуулна.

Зураг бүрийн хувьд зурагны байрлал босоо эсвэл хэвтээ эсэх нь мэдэгдэж байгаа. Гар утас босоо байрлалтай байгаа ба үүнийг өөрчилж болохгүй. Зурагны байрлалыг солиход (босоогоос хэвтээ уруу эсвэл хэвтээгээс босооруу) $b$ секунд зарцуулна.

Васяд нийт зурагнуудыг үзэхэд $T$ секунд байгаа. Тэр аль болох олон зураг үзэхийг хүсч байгаа. Хэрвээ Вася зургийг эхний удаа нээж байгаа бол зурагны доторх бүх зүйлийг ажиглахад $1$ секунд. Хэрвээ зураг буруу байрлалтай байвал Вася зургийг үзэхээс өмнө байрлалыг эргүүлэх хугацаа нь $b$ секунд болно. Хэрвээ Вася зургийг аль хэдийн нээчихсэн бол үүнийг алгасна(зурагны байрлалыг өөрчлөх эсвэл үзэх гэж цаг зарцуулахгүй гэсэн үг). Анх удаа нээж буй зургийг алгасаж болохгүй.

Васяд $T$ секундын хугацаанд үзэх боломжтой нийт зурагны хамгийн их тоог ол.

Оролт

Оролтын эхний мөрөнд 4 бүхэл тоон утгууд болох $n, a, b, T$ ($1 ≤ n ≤ 5*10^{5}$, $1 ≤ a, b ≤ 1000$, $1 ≤ T ≤ 10^{9}$) ба харгалзан зургуудын тоо, хөрш зурагруу шилжих хугацаа, зурагны байрлалыг өөрчлөх хугацаа ба Васягийн зураг үзэхэд зарцуулах нийт хугацаа байна.

Оролтын хоёр дахь мөрөнд '$w$' болон '$h$' тэмдэгтүүдээс тогтох $n$ урттай тэмдэгт мөр байна.

Хэрвээ тэмдэгт мөрийн $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 секунд зарцуулна.

Сүүлийн жишээн дээр та эхний зургийг үзэж амжихгүй ба бас эхний зургийг алгасаж болохгүй.

Сэтгэгдлүүдийг ачааллаж байна...