B - Fruit Harvest Season Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は果樹園を経営しています。今年の収穫シーズンは N 日間あり、各日の天気はすでに確定しています。天気は各日について「晴れ」「曇り」「雨」のいずれかであり、i 日目の天気を W_i で表します。W_i が S のとき晴れ、C のとき曇り、R のとき雨を意味します。

果物の収穫作業は晴れの日にしか行うことができません。高橋君はアルバイトを雇うために、N 日間の中から連続する K 日間をちょうど 1 つ選んで勤務期間とする契約を結びます。すなわち、ある整数 d（1 \leq d \leq N - K + 1）を選び、第 d 日目から第 d + K - 1 日目までをアルバイトの勤務期間とします。

高橋君は、選んだ K 日間に含まれる晴れの日の数ができるだけ多くなるように期間を選びたいです。

N 日間の天気が与えられたとき、連続する K 日間の選び方すべてのうち、その区間に含まれる晴れの日数の最大値を求めてください。

制約

  • 1 \leq K \leq N \leq 10^6
  • N, K は整数である。
  • W_i（1 \leq i \leq N）は S, C, R のいずれかである。

入力

N K
W_1 W_2 \ldots W_N
  • 1 行目には、収穫シーズンの日数を表す整数 N と、アルバイトを雇う連続日数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各日の天気を表す W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。
  • W_i は i 日目の天気を表し、 S は晴れ、 C は曇り、 R は雨を意味する。

出力

連続する K 日間の選び方すべてのうち、その区間に含まれる晴れの日数の最大値を 1 行で出力してください。

入力例 1

7 3
S C S S R S C

出力例 1

2

入力例 2

5 3
R C R C R

出力例 2

0

入力例 3

15 5
S S C R S S S C R R S S S S C

出力例 3

4

入力例 4

30 7
S C S S R S S S C R S S S S R C S S S R S C S S S S C R S S

出力例 4

5

入力例 5

1 1
S

出力例 5

1

Score : 300 pts

Problem Statement

Takahashi runs an orchard. This year's harvest season lasts N days, and the weather for each day has already been determined. The weather for each day is one of "sunny," "cloudy," or "rainy," and the weather on day i is represented by W_i. W_i is S for sunny, C for cloudy, and R for rainy.

Fruit harvesting can only be done on sunny days. To hire a part-time worker, Takahashi will sign a contract that selects exactly one period of K consecutive days from the N days as the work period. That is, he chooses an integer d (1 \leq d \leq N - K + 1) and sets the work period from day d to day d + K - 1.

Takahashi wants to choose the period so that the number of sunny days included in the chosen K days is as large as possible.

Given the weather for all N days, find the maximum number of sunny days contained in any selection of K consecutive days.

Constraints

  • 1 \leq K \leq N \leq 10^6
  • N, K are integers.
  • W_i (1 \leq i \leq N) is one of S, C, R.

Input

N K
W_1 W_2 \ldots W_N
  • The first line contains an integer N representing the number of days in the harvest season and an integer K representing the number of consecutive days to hire the part-time worker, separated by a space.
  • The second line contains W_1, W_2, \ldots, W_N representing the weather for each day, separated by spaces.
  • W_i represents the weather on day i, where S means sunny, C means cloudy, and R means rainy.

Output

Print in one line the maximum number of sunny days contained in any selection of K consecutive days.

Sample Input 1

7 3
S C S S R S C

Sample Output 1

2

Sample Input 2

5 3
R C R C R

Sample Output 2

0

Sample Input 3

15 5
S S C R S S S C R R S S S S C

Sample Output 3

4

Sample Input 4

30 7
S C S S R S S S C R S S S S R C S S S R S C S S S S C R S S

Sample Output 4

5

Sample Input 5

1 1
S

Sample Output 5

1