#P1314. River过河

River过河

Description

ZY带N个小Kid过河,小KID分成两种:高一年级,高二年级,由于存在代沟问题,如果同一条船上高一年级生和高二年级

生数量之差超过K,就会发生不和谐的事件.当然如果一条船上全是同一年级的,就绝对不会发生争执.现在ZY按小KID

队列的顺序依次安排上船,并且不能让他们在过河时发生争执.对于当前等待上船的小KID来说,要么让他上船,要么

将停在渡口的船开走,再让他上另一条船,同一条船上的人不过超过M人.为了让所有的小KID过河,在知悉小KID队列

的情况下,最少需要多少条船.

Input

第一行给出N,M,K.含义如上所述

下行N行用来描述小KID的队列,每行一个字符”A”或者”L”

1<=N<=250000,1<=M,K<=N

Output

最少需要多少条船

Samples

5 4 1
A
L
L
L
A
2