시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 67 12 9 20.455%

문제

동혁이는 자석을 매우 좋아하고, 자석을 이용해서 매우 독특한 실험을 한다. 동혁이가 가지고 있는 자석은 작은 막대처럼 생겼다. 자석은 길이가 1이고, 두 자극(S극과 N극)을 가지고 있다. 자석은 같은 극끼리는 붙지 않지만, 다른 극끼리는 서로 붙는다. 이 자석은 매우 강력한 자석이기 때문에, 한 번 붙으면 다시 뗄 수 없다.

실험을 시작하기 전에 동혁이는 N개의 자석을 바닥에 놓는다. 그 다음 실험을 시작하면 다른 극을 마주 보고 있는 자석은 모두 붙는다. 자석은 실험을 시작하기 전에는 붙지 않는다. 또, 실험을 시작한 후, 붙은 자석은 뗄 수 없다.

예를 들어, 동혁이가 실험을 시작하기 전에 자석 6개를 다음과 같이 놓았다고 생각해보자.

동혁이가 실험을 시작하면, 자석은 다음과 같이 붙게된다.

사실 동혁이는 길이가 정확히 L인 자석이 필요해서 이 실험을 시작하게 된 것이다. 동혁이가 자석을 놓은 초기 배치가 주어졌을 때, 몇 개의 자석을 뒤집으면 길이가 정확히 L인 자석을 얻을 수 있는지 구하는 프로그램을 작성하시오. 만약, 여러가지 경우가 있다면 뒤집는 횟수가 가장 작은 것을 출력한다.

입력

첫째 줄에 자석의 수 N과 동혁이가 만드려고 하는 자석의 길이 L이 주어진다. (1 ≤ N ≤ 500000, 1 ≤ L ≤ N)

다음 줄에는 초기 자석의 배치를 나타내는 문자열 "NS" 또는 "SN"이 N개가 주어진다.

항상 답이 존재하는 경우만 주어진다.

출력

길이가 정확히 L인 자석을 만들기 위해서 필요한 뒤집는 횟수의 최소값을 출력한다.

예제 입력 1

6 4
NS SN NS SN SN NS

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjMxNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWMxMWQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViOWU0XHVjNmIwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWNlMCwgXHVjNzkwXHVjMTFkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5ZTRcdWM2YjAgXHViM2M1XHVkMmI5XHVkNTVjIFx1YzJlNFx1ZDVkOFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1Yzc5MFx1YzExZFx1Yzc0MCBcdWM3OTFcdWM3NDAgXHViOWM5XHViMzAwXHVjYzk4XHViN2ZjIFx1YzBkZFx1YWNiY1x1YjJlNC4gXHVjNzkwXHVjMTFkXHVjNzQwIFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHVjNzkwXHVhZGY5KFNcdWFkZjlcdWFjZmMgTlx1YWRmOSlcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzkwXHVjMTFkXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWFkZjlcdWIwN2NcdWI5YWNcdWIyOTQgXHViZDk5XHVjOWMwIFx1YzU0YVx1YzljMFx1YjljYywgXHViMmU0XHViOTc4IFx1YWRmOVx1YjA3Y1x1YjlhY1x1YjI5NCBcdWMxMWNcdWI4NWMgXHViZDk5XHViMjk0XHViMmU0LiBcdWM3NzQgXHVjNzkwXHVjMTFkXHVjNzQwIFx1YjllNFx1YzZiMCBcdWFjMTVcdWI4MjVcdWQ1NWMgXHVjNzkwXHVjMTFkXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVkNTVjIFx1YmM4OCBcdWJkOTlcdWM3M2NcdWJhNzQgXHViMmU0XHVjMmRjIFx1YjVjNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViYzE0XHViMmU1XHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWFkZjlcdWM3NDQgXHViOWM4XHVjOGZjIFx1YmNmNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNzkwXHVjMTFkXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJkOTlcdWIyOTRcdWIyZTQuIFx1Yzc5MFx1YzExZFx1Yzc0MCBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMFx1YjI5NCBcdWJkOTlcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI2MTAsIFx1YzJlNFx1ZDVkOFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVkNmM0LCBcdWJkOTlcdWM3NDAgXHVjNzkwXHVjMTFkXHVjNzQwIFx1YjVjNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjMmU0XHVkNWQ4XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVjNzkwXHVjMTFkIDZcdWFjMWNcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWIxOTNcdWM1NThcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL25zLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDUyMnB4OyBoZWlnaHQ6IDQ2cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0LCBcdWM3OTBcdWMxMWRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJkOTlcdWFjOGNcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbnNucy5wbmdcIiBzdHlsZT1cIndpZHRoOiA1MDdweDsgaGVpZ2h0OiA0NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYWNcdWMyZTQgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggTFx1Yzc3OCBcdWM3OTBcdWMxMWRcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTc0XHVjMTFjIFx1Yzc3NCBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhYzhjIFx1YjQxYyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViMTkzXHVjNzQwIFx1Y2QwOFx1YWUzMCBcdWJjMzBcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViNGE0XHVjOWQxXHVjNzNjXHViYTc0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggTFx1Yzc3OCBcdWM3OTBcdWMxMWRcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjljY1x1YzU3ZCwgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHViNGE0XHVjOWQxXHViMjk0IFx1ZDY5Zlx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc5MFx1YzExZFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWM3OTBcdWMxMWRcdWM3NTggXHVhZTM4XHVjNzc0IExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA1MDAwMDAsIDEgJmxlOyBMICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNkMDhcdWFlMzAgXHVjNzkwXHVjMTFkXHVjNzU4IFx1YmMzMFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0ICZxdW90O05TJnF1b3Q7IFx1YjYxMFx1YjI5NCAmcXVvdDtTTiZxdW90O1x1Yzc3NCBOXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFlMzhcdWM3NzRcdWFjMDAgXHVjODE1XHVkNjU1XHVkNzg4IExcdWM3NzggXHVjNzkwXHVjMTFkXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjRhNFx1YzlkMVx1YjI5NCBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUFHTkVUSSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNyYXp5IHNjaWVudGlzdCBNYXRpamEgaXMgcGVyZm9ybWluZyBjcmF6eSBleHBlcmltZW50cyB3aXRoIGV2ZW4gY3JhemllciBtYWduZXRzLiBFYWNoIG1hZ25ldCBsb29rcyBsaWtlIGEgc21hbGwgc3RpY2suIEl0IGlzIDEgdW5pdCBsb25nIGFuZCBoYXMgdHdvIG1hZ25ldGljIHBvbGVzLCBTb3V0aCAoUykgYW5kIE5vcnRoIChOKS4gUG9sZXMgb2YgdHdvIG1hZ25ldHMgd2l0aCB0aGUgc2FtZSBvcmllbnRhdGlvbiBjYW5ub3QgYmUgam9pbmVkLCBidXQgb3Bwb3NpdGUgcG9sZXMgYXR0cmFjdCBlYWNoIG90aGVyIGFuZCBtYWtlIHRoZSBtYWduZXRzIGpvaW4uIFRoZSBtYWduZXRzIGFyZSBzbyBzdHJvbmcgdGhhdCBldmVuIENodWNrIE5vcnJpcyBjYW5ub3Qgc2VwYXJhdGUgdGhlbSBvbmNlIHRoZXkgaGF2ZSBqb2luZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJlZm9yZSB0aGUgZXhwZXJpbWVudCBzdGFydHMsIE1hdGlqYSBwdXRzIE4gbWFnbmV0cyBvbiB0aGUgZmxvb3Igb2YgaGlzIGxhYm9yYXRvcnksIGxpa2UgdGhpczombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ucy5wbmdcIiBzdHlsZT1cImhlaWdodDo0NnB4OyB3aWR0aDo1MjJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5CZWZvcmUgTWF0aWphIGNhbiBwcm9jZWVkLCBvcHBvc2l0ZSBwb2xlcyBvZiBuZWlnaGJvdXJpbmcgbWFnbmV0cyBhdHRyYXQgZWFjaCBvdGhlciBhbmQgdGhvc2UgbWFnbmV0cyBqb2luLCBmb3JtaW5nIGEgc2luZ2xlIGluc2VwYXJhYmxlIG1hZ25ldC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9uc25zLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjQ0cHg7IHdpZHRoOjUwN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkhlIG5vdGljZWQgdGhhdCBieSBmbGlwcGluZyBhIG1hZ25ldCBpbiB0aGUgbmV3IHNlcXVlbmNlLCBoZSBjYW4gY2F1c2UgbW9yZSBtYWduZXRzIHRvIGpvaW4uIEhlIGRlY2lkZWQgdG8gY3JlYXRlIGEgbWFnbmV0IGV4YWN0bHkgTCB1bml0cyBsb25nLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgZmxpcCBvcGVyYXRpb25zIG5lZWRlZCB0byBnZXQgYSBtYWduZXQgb2YgbGVuZ3RoIEwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTCAoMSAmbGU7IE4gJmxlOyA1MDAgMDAwLCAxICZsZTsgTCAmbGU7IE4pLCB0aGUgbnVtYmVyIG9mIHN0YXJ0aW5nIG1hZ25ldHMgYW5kIHRoZSByZXF1aXJlZCBsZW5ndGguIFRoZSBzdGFydGluZyBtYWduZXRzIGFyZSAxIHVuaXQgbG9uZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBOIHN0cmluZ3MgJnF1b3Q7TlMmcXVvdDsgb3IgJnF1b3Q7U04mcXVvdDssIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBUaGVzZSBhcmUgdGhlIG9yaWVudGF0aW9ucyBvZiB0aGUgbWFnbmV0cyBhZnRlciBNYXRpamEgcHV0cyB0aGVtIG9uIHRoZSBmbG9vciwgYnV0IGJlZm9yZSB0aGUgaW5pdGlhbCBqb2luaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCBhIHNvbHV0aW9uIHdpbGwgYWx3YXlzIGV4aXN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBpbiA3MCUgb2YgdGhlIG9mZmljaWFsIHRlc3QgZGF0YSwgTiB3aWxsIGJlIGxlc3MgdGhhbiAxMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGZsaXBzIG5lZWRlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=