题目描述

春季郊野,万木吐翠,芳草茵茵,百鸟争鸣,阳光和煦,空气清新,置身于这如诗如两的环 境中,能使人心胸开阔,疲劳消除,精神振奋，话说魔法学院每年都会组织学员外出春游。他 们春游的地点非常遇远,所以学院安排的交通工具是火车!现在所有的同学都已经在火车 站进站口等待了，一共$\red{n}$名同学,他们排成了一行按照这个顺序登车。一节火车厢最多可以 容纳$\red{m}$名同学,但是由于某种奇特的原因,一节车厢里只允许要么所有的同学都是同一种 性别,要么男生和女生的人数差不能超过$\red{k,}$现在请问学院该怎样安排同学们才能使得用到 的车厢尽量的少呢?

输入格式

第一行三个数，分别表示$\red{n (n≤}$$\red{1 000),m}$和$\red{k}$。 接下来$\red{n}$行描述排队的顺序，每行一个字母,表示是$\red{B(boy)}$或者是$\red{G(girl)}$。

输出格式

一个整数表示至少需要的车厢数。

样例

输入样例

5 4 1
B
G
G
G
B

输出样例

2