32119번 - 러시안 회전초밥

문제

진우는 세계 최고의 도박사이자 미식가이다. 진우는 좋아하는 아이돌 그룹의 사장인 도현이 “러시안 회전초밥”이라는 음식점을 새롭게 개업했다는 소식을 듣고 한 걸음에 달려갔다.

러시안 회전초밥의 대표 메뉴는, 당연하게도, 러시안 회전초밥이다. 이 메뉴를 주문하면 $N$개의 초밥과 함께 챌린지가 주어지는데, 챌린지에 성공한 도전자는 돈을 내지 않아도 된다. 챌린지의 목표는 한 번도 표정이 변하지 않고 $K$개의 초밥을 먹는 것이다. 이 챌린지가 어려운 이유는 몇몇 초밥에 매운 와사비가 듬뿍 들어가기 때문이다!

챌린지는 다음과 같이 진행된다. 먼저 도현은 원형 컨베이어 벨트 위에 일정한 간격으로 $N$개의 초밥을 배치한다. 도현은 도전자가 보는 앞에서 초밥 몇 개에 와사비를 넣어서 그 위치를 알 수 있게 한다. 와사비 초밥을 포함해서 모든 초밥은 생김새가 동일하여 구분할 수 없다.

그 다음 도전자는 눈을 가리고, 도현은 컨베이어 벨트를 무작위로 회전시킨다. 도전자가 다시 눈을 뜨면 컨베이어 벨트가 시계 방향으로 돌아가기 시작한다. 이제부터 도전자는 자신의 앞에 초밥이 놓일 때마다 즉시 그 초밥을 먹어야 한다. 즉, 도전자는 눈을 뜬 순간 앞에 놓인 초밥부터 반시계 방향으로 연속한 초밥을 먹게 된다.

컨베이어 벨트를 무작위로 회전한 후, 눈을 뜨면 초밥을 반시계 방향으로 먹게 됨

도현은 더 많은 사람들에게 기회를 주기 위해 초밥 건너뛰기 쿠폰을 판매하고 있다. 도전자는 눈을 가리기 전에 쿠폰을 원하는 만큼 살 수 있다. 도전자가 쿠폰을 사용하면 앞에 놓인 초밥 하나를 먹지 않고 건너뛸 수 있다. 이렇게 건너뛴 초밥은 컨베이어 벨트에서 제거되며, 도현이 확인해서 와사비가 들었는지 알려준다.

도전자가 와사비 초밥을 먹고 표정이 변하거나, 초밥을 너무 많이 건너뛰어서 $K$개의 초밥을 먹지 못하면 챌린지에 실패한다.

진우는 러시안 회전초밥 챌린지에 도전하려고 한다. 안타깝게도 진우는 매운 음식을 못 먹기 때문에 와사비 초밥은 피해야 한다. 진우는 세계 최고의 도박사이자 미식가라는 명성을 잃고 싶지 않으므로, 어떤 경우에도 챌린지에 실패하는 일이 없도록 충분한 양의 쿠폰을 구매하려고 한다.

진우가 눈을 가리기 전에 확인한 와사비 초밥의 위치가 주어진다. 진우가 최선의 전략으로 챌린지에 도전한다면, 최소 몇 개의 쿠폰을 구매해야 반드시 챌린지에 성공할 수 있을까?

입력

첫 줄에 초밥의 개수 $N$과 챌린지에서 먹어야 하는 초밥의 개수 $K$가 공백을 사이에 두고 주어진다. $(1\le K\le N\le 200,円 000)$

둘째 줄에 문자 O와 X로 구성된 길이 $N$의 문자열이 주어진다. $i$번째 문자는 진우가 눈을 가리기 전에 반시계 방향으로 $i$번째 위치에 놓인 초밥이 와사비 초밥인지를 나타낸다. O는 와사비 초밥을, X는 와사비가 들지 않은 초밥을 나타낸다.

출력

진우가 반드시 챌린지에 성공하기 위해서 최소 몇 개의 쿠폰을 구매해야 하는지를 출력한다. 만약 몇 개의 쿠폰을 구매하더라도 챌린지에 실패할 가능성이 있다면, 대신 -1을 출력한다.

제한

힌트