MAGNETI

문제

The crazy scientist Matija is performing crazy experiments with even crazier magnets. Each magnet looks like a small stick. It is 1 unit long and has two magnetic poles, South (S) and North (N). Poles of two magnets with the same orientation cannot be joined, but opposite poles attract each other and make the magnets join. The magnets are so strong that even Chuck Norris cannot separate them once they have joined. 

Before the experiment starts, Matija puts N magnets on the floor of his laboratory, like this: 

[이미지 1]

Before Matija can proceed, opposite poles of neighbouring magnets attrat each other and those magnets join, forming a single inseparable magnet. 

[이미지 2]

He noticed that by flipping a magnet in the new sequence, he can cause more magnets to join. He decided to create a magnet exactly L units long. Write a program that determines the smallest number of flip operations needed to get a magnet of length L. 

입력

The first line of input contains two integers N and L (1 ≤ N ≤ 500 000, 1 ≤ L ≤ N), the number of starting magnets and the required length. The starting magnets are 1 unit long. 

The next line contains N strings "NS" or "SN", separated by single spaces. These are the orientations of the magnets after Matija puts them on the floor, but before the initial joining. 

The input data will be such that a solution will always exist. 

Note: in 70% of the official test data, N will be less than 1000. 

출력

Output the smallest number of flips needed.

힌트

Clarification for first sample: the fourth and fifth magnets immediately join. If Matija flips that 2 unit long magnet, it will connect to both neighbouring magnets, forming a magnet of length 4.