题目描述

ZY带N个小Kid过河,小KID分成两种:高一年级,高二年级,由于存在代沟问题,如果同一条船上高一年级生和高二年级生数量之差超过K,就会发生不和谐的事件.当然如果一条船上全是同一年级的,就绝对不会发生争执.现在ZY按小KID队列的顺序依次安排上船,并且不能让他们在过河时发生争执.对于当前等待上船的小KID来说,要么让他上船,要么将停在渡口的船开走,再让他上另一条船,同一条船上的人不过超过M人.为了让所有的小KID过河,在知悉小KID队列的情况下,最少需要多少条船.

输入格式

第一行给出N,M,K.含义如上所述 下行N行用来描述小KID的队列,每行一个字符”A”或者”L”

输出格式

最少需要多少条船

5 4 1
A
L
L
L
A

2

提示

前三个人一条船,后两个人一条船 数据范围 30% 数据中1<=N<=1000 100%数据中1<=N<=250000,1<=M,K<=N

题目来源

没有写明来源