Problem Description

In order to combat potato cruelty in Potatoland, Jiahai is running for election. Jiahai has one competitor, Guan, who is trying to win the election as well. Potatoland consists of a series of N small houses on a straight main road, numbered from 0 to N-1. Before the election, Jiahai has already conducted polls and has found out who each house will vote for.

However, here is the problem. The electorial system is really stupid, and it allows Jiahai to split this road up into segments of at least length L where each segment constitutes an "electorial division". Each electorial division will cast one electorial vote based on its majority. (If Jiahai wins exactly half, Guan has the majority) Jiahai wants to maximise his winning margin, which is defined as (number of electorial votes cast for Jiahai) - (number of electorial votes cast for Guan). Help Jiahai find out what is the maximum possible winning margin. (It can be negative, if Jiahai is sure to lose.)


The first line of input will contain two integers, N and L.
The second line of input will contain N characters, each of them either 'J' or 'G', depending on who the house will vote for.


The output should contain one line with one integer only, representing Jiahai's maximum winning margin.


Subtask 1 (11%): 1 ≤ N, L ≤ 20.
Subtask 2 (21%): 1 ≤ N, L ≤ 3 000.
Subtask 3 (31%): 1 ≤ N ≤ 300 000. L = 1.
Subtask 4 (37%): 1 ≤ N, L ≤ 300 000.
Subtask 5 (0%): Sample testcases.

Sample Input 1

8 3

Sample Output 1


Sample Input 2

13 3

Sample Output 2


Submitting .cpp to 'election'

You're not logged in! Click here to login

Compile Errors

Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 26
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 11
2 21
3 31
4 37
5 0