라라와 용맥 변환

여러분, 그거 알아요?

자연에서 태어난 모든 생명들은 바람과 물로 이루어져 햇빛을 받아 이 땅에 존재한다고 해요. 그래서 땅을 보면 우리가 어떻게 살아야 하는지 알 수 있대요.

바람처럼 열린 마음으로 날아오르고 강처럼 쉬지 않고 앞으로 나아가다가 햇빛처럼 괴로운 마음들을 따뜻하게 달래 주고 산처럼 고요히 머무르다 가면 되는 거래요.

-라라 튜토리얼 스토리 중-

메이플스토리의 직업 라라는 용맥 분출이라는 스킬로 사냥한다.

라라는 해, 강, 바람의 세 종류 용맥을 발견할 수 있다. 용맥 분출을 사용하면 용맥을 소모하여 그 위치에 토지령이라는 소환수를 불러내고, 토지령은 그 위치에 지속적으로 데미지를 준다. 토지령도 해, 강, 바람의 세 종류가 있으며, 소모한 용맥과 같은 종류의 토지령이 소환된다. 각 토지령은 종류별로 한 마리씩만 소환할 수 있다. 같은 종류의 토지령이 이미 소환되어 있을 때 토지령을 소환하면 기존의 같은 종류 토지령은 사라지고, 종류별로 가장 마지막에 소환된 토지령만 남는다.

예를 들어 해의 토지령과 강의 토지령이 소환되어 있는 상태에서 용맥 분출로 바람 용맥을 소모하면, 그 위치에 바람의 토지령이 소환된다. 해 용맥을 소모하면 기존의 해의 토지령이 사라지고 새로운 해의 토지령이 소환된다. 강의 토지령과 바람의 토지령은 해의 토지령과 종류가 다르므로 사라지지 않는다.

용맥 분출에는 단점이 하나 있다. 적절한 종류의 용맥을 소모하지 못하면 소환한 토지령이 너무 빨리 사라져 몬스터에게 충분한 데미지를 주지 못할 수 있다. 이를 보완하기 위해 라라는 또 다른 스킬인 용맥 변환을 가지고 있다. 용맥 변환을 사용할 때마다 원하는 위치의 용맥 하나를 원하는 다른 종류의 용맥으로 바꿀 수 있다.

예를 들어 해 용맥, 해 용맥, 해 용맥이 순서대로 있을 때, 두 번째 용맥에 용맥 변환을 사용해 바람 용맥으로 바꿀 수 있다. 이 경우 용맥의 배치는 해 용맥, 바람 용맥, 해 용맥이 된다. 이어서 세 번째 용맥에 용맥 변환을 사용해 강 용맥으로 바꾸면, 용맥의 배치는 해 용맥, 바람 용맥, 강 용맥이 된다.

라라는 $N$개의 용맥이 일렬로 있고, 각 용맥마다 체력이 $H$인 몬스터가 한 마리씩 있는 직선형 맵에서 사냥하려고 한다. 라라는 맵의 가장 왼쪽 용맥에서 시작하며, 다음 과정이 반복되어 사냥이 진행된다.

1. 라라가 현재 위치한 곳의 용맥을 소모하여 용맥 분출을 한다. 소모한 용맥에 따른 토지령이 소환되고, 기존에 소환되어 있던 같은 종류의 토지령은 즉시 사라진다.
2. 현재 소환되어 있는 모든 토지령이 그 위치에 있는 몬스터에게 데미지를 주고, 체력을 $1$ 감소시킨다. 몬스터의 체력이 $0$이 되면 그 몬스터는 처치된다.
3. 라라가 오른쪽으로 인접한 용맥으로 이동한다. 이동할 수 있다면 반드시 이동한다. 맵의 오른쪽 끝에 도달해 이동할 용맥이 없다면, 현재 토지령이 소환되어 있는 위치의 몬스터가 모두 처치되고 사냥이 끝난다.

라라는 맵에 있는 모든 몬스터를 처치하기 위해 사냥을 시작하기 전에 용맥 변환으로 용맥의 종류를 바꾼다. 용맥 변환에는 쿨타임이 있으므로, 빠른 사냥을 위해 최소한의 횟수만 사용한다.

맵의 모든 몬스터를 처치하면서 용맥 변환을 최소한으로 사용할 때의 횟수를 라라에게 알려주자.

입력

첫 번째 줄에는 맵에 있는 용맥의 수 $N$과 몬스터의 체력 $H$가 공백으로 구분되어 주어진다. $(1 \le N, H \le 1\,000\,000)$

두 번째 줄에는 용맥의 종류를 순서대로 나타내는 길이 $N$의 공백 없는 문자열이 주어진다.

문자열은 S, R, W로만 이루어져 있으며, 각각 용맥의 세 종류인 해, 강, 바람을 나타낸다.

출력

맵의 모든 몬스터를 처치하기 위해 사용해야 하는 용맥 변환 횟수의 최솟값을 출력한다.

아무리 많은 용맥 변환을 사용해도 맵의 모든 몬스터를 처치할 수 없다면 대신 -1을 출력한다.

맵의 모든 몬스터를 처치하기 위해 사용해야 하는 용맥 변환 횟수의 최솟값을 출력한다. 아무리 많은 용맥 변환을 사용해도 모든 몬스터를 처치할 수 없다면 -1을 출력한다.