D. Хүн бүрт амттан!

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

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

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

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

Түүний мэдэж байгаа зүйл нь Хюүмилийн доор байх Хюү бүр чимэглэл өлгөөд завгүй байв. "Тэд чимэглэлээ өлгөж байна!" гэж шоолонгуй ярвайв, "Маргааш Зул сарын баяр, Бараг болох гэж байна!"

Доктор Суэс, Гринч зул сарыг хулгайлсан нь

Хөүвилд зул сарын баяр ирж байна. Синди Люү Хөү ба түүний эцэг эх Люү Люү Хөү ба Бетти Люү Хөү нар гудамжныхаа бүх хүнд амттан өгөхөөр шийдсэн. Тэд гудамжны байшин бүрийн оршин суугчдад нэг килограмм амттан өгөхөөр шийдсэн. Иймээс тэдэнд байшингийн тоотой тэнцүү килограмм амттан хэрэгтэй.

Люү Хөү-н гэр бүлийн амьдардаг гудамжыг тэнцүү урттай үргэлжилсэн $n$ хэсэг хэлбэрээр дүрсэлж болно. Та дурын хэсгээс хөрш хэсэгрүү нэгж хугацаанд очиж чадна. Хэсэг бүр дараах гурван төрлийн аль нэг нь байна: хоосон газар, байшин эсвэл дэлгүүр. Синди Люү ба түүний гэр бүл дэлгүүрээс амттан авч болох боловч нэг дэлгүүрт нэг килограмм л амттан байдаг (худалдагч нар Хөүвилийн оршин суугчдыг амттан хэтрүүлэн идэхээс сэргийлдэг).

Люү Хөү-н гэр бүл гэрээсээ гарсны дараа тэд замын эхний хэсэгт байх болно. Замын уг хэсэгт хүрэхэд ч тэд мөн нэгж хугацаа зарцуулна. Бид Синди болон түүний ээж, аав хэдэн ч клограмм амттан авч явж чадна гэж үзнэ. Тэд байшинтай хэсэгт байх бүртээ оршин суугчдад нэг килограмм амттан өгнө эсвэл зүгээр өөр хэсэгрүү явж болно. Хэрвээ гэр бүл байшингийн оршин суугчдад амттанаа аль хэдийн өгчихсөн бол дахин өгч чадахгүй. Үүнтэй адилаар хэрвээ тэд дэлгүүртэй хэсэгт байвал дэлгүүрээс нэг килограмм амттан авна эсвэл уг дэлгүүрийг алгасаж болно. Хэрвээ тэд дэлгүүрээс амттан авсан бол худалдагч тэднийг санах ба дахин ирвэл ширхэг чихэр ч зарахгүй болно. Амттан худалдан авах болон өгөх хугацааг тооцохгүй. Люү Хөүгийнхэн ямар ч байшинг хоосон үлдээхийг хүссэнгүй.

Тэдэнд зул сарын баярт бэлдэх хугацаа хэрэгтэй тул амттанаа тараахдаа $t$-с илүү нэгж хугацаа зарцуулахыг хүсэхгүй байна. Бүх амттанаа тараах хугацаа хэрэгтэй учир тэд эхэндээ гэрээсээ $k$ килограмм амттан авч явах хэрэгтэй болж болно.

Синди Люү тэдний явч явах шаардлагатай амттаны хэмжээ болох $k$ тооны хамгийн бага утгыг олохыг хүсч байна.

Таны ажил бол боломжит хамгийн бага $k$ утгыг тодорхойлдог програм бичих юм.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ба $t$ ($2 ≤ n ≤ 5*10^{5}, 1 ≤ t ≤ 10^{9}$) байна. Хоёр дахь мөрөнд $n$ тэмдэгт байх ба хэрвээ $i$-р хэсэгт байшин байвал $i$-р тэмдэгт "$H$" байна. Хэрвээ дэлгүүр байвал "$S$" байна, харин хоосон газар байвал "$.$" байна.

Ядаж нэг байшинтай хэсэг байх нь тодорхой.

Гаралт

Хэрвээ хамгийн ихдээ $t$ хугацааны нэгжид багтан хүн бүрт амттан өгөх боломжгүй бол "$-1$"-г (хашилтгүйгээр) хэвлэ. Бусад тохиолдолд боломжит хамгийн бага $k$-н утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
6 6
HSHSHS
Гаралт
1
Оролт
14 100
...HHHSSS...SH
Гаралт
0
Оролт
23 50
HHSS.......SSHHHHHHHHHH
Гаралт
8

Тэмдэглэл

Эхний жишээн дээр ижил тооны байшин болон дэлгүүр байна. Хэрвээ тэд гэрээсээ ямар ч амттан авч явахгүй бол эхний байшингийн оршин суугчдад бэлэг өгөхийн тулд тэд хамгийн багадаа нэг алхам ухрах хэрэгтэй ба тэдэнд ийм цаг байхгүй. Хэрвээ тэд нэг килограмм амттан авч явбал буцаж явахгүй.

Хоёр дахь жишээн дээр дэлгүүр болон байшингийн тоо тэнцүү ба хангалттай цаг байна. Нэг чиглэлд явахдаа таарсан бүх дэлгүүрээс амттан аваад буцахдаа тарааж өгнө.

Гурав дахь жишээн дээр гудамжинд байгаа дэлгүүрийн тоо нь байшингийн тооноос бага байна. Люү Хөүгийн гэр бүл гэрээсээ дутуу байгаа тоо бүрээр нэг килограмм амттан авах хэрэгтэй.

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