시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHRcdWMwYWNcdWMyZTQgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggTFx1Yzc3OCBcdWM3OTBcdWMxMWRcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTc0XHVjMTFjIFx1Yzc3NCBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhYzhjIFx1YjQxYyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViMTkzXHVjNzQwIFx1Y2QwOFx1YWUzMCBcdWJjMzBcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViNGE0XHVjOWQxXHVjNzNjXHViYTc0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggTFx1Yzc3OCBcdWM3OTBcdWMxMWRcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjljY1x1YzU3ZCwgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0IFx1YjRhNFx1YzlkMVx1YjI5NCBcdWQ2OWZcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3OTBcdWMxMWRcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVjNzkwXHVjMTFkXHVjNzU4IFx1YWUzOFx1Yzc3NCBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAwMDAwLCAxICZsZTsgTCAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDA4XHVhZTMwIFx1Yzc5MFx1YzExZFx1Yzc1OCBcdWJjMzBcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCAmcXVvdDtOUyZxdW90OyBcdWI2MTBcdWIyOTQgJnF1b3Q7U04mcXVvdDtcdWM3NzQgTlx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhZTM4XHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBMXHVjNzc4IFx1Yzc5MFx1YzExZFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BR05FVEkiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjcmF6eSBzY2llbnRpc3QgTWF0aWphIGlzIHBlcmZvcm1pbmcgY3JhenkgZXhwZXJpbWVudHMgd2l0aCBldmVuIGNyYXppZXIgbWFnbmV0cy4gRWFjaCBtYWduZXQgbG9va3MgbGlrZSBhIHNtYWxsIHN0aWNrLiBJdCBpcyAxIHVuaXQgbG9uZyBhbmQgaGFzIHR3byBtYWduZXRpYyBwb2xlcywgU291dGggKFMpIGFuZCBOb3J0aCAoTikuIFBvbGVzIG9mIHR3byBtYWduZXRzIHdpdGggdGhlIHNhbWUgb3JpZW50YXRpb24gY2Fubm90IGJlIGpvaW5lZCwgYnV0IG9wcG9zaXRlIHBvbGVzIGF0dHJhY3QgZWFjaCBvdGhlciBhbmQgbWFrZSB0aGUgbWFnbmV0cyBqb2luLiBUaGUgbWFnbmV0cyBhcmUgc28gc3Ryb25nIHRoYXQgZXZlbiBDaHVjayBOb3JyaXMgY2Fubm90IHNlcGFyYXRlIHRoZW0gb25jZSB0aGV5IGhhdmUgam9pbmVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5CZWZvcmUgdGhlIGV4cGVyaW1lbnQgc3RhcnRzLCBNYXRpamEgcHV0cyBOIG1hZ25ldHMgb24gdGhlIGZsb29yIG9mIGhpcyBsYWJvcmF0b3J5LCBsaWtlIHRoaXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbnMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NDZweDsgd2lkdGg6NTIycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QmVmb3JlIE1hdGlqYSBjYW4gcHJvY2VlZCwgb3Bwb3NpdGUgcG9sZXMgb2YgbmVpZ2hib3VyaW5nIG1hZ25ldHMgYXR0cmF0IGVhY2ggb3RoZXIgYW5kIHRob3NlIG1hZ25ldHMgam9pbiwgZm9ybWluZyBhIHNpbmdsZSBpbnNlcGFyYWJsZSBtYWduZXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbnNucy5wbmdcIiBzdHlsZT1cImhlaWdodDo0NHB4OyB3aWR0aDo1MDdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5IZSBub3RpY2VkIHRoYXQgYnkgZmxpcHBpbmcgYSBtYWduZXQgaW4gdGhlIG5ldyBzZXF1ZW5jZSwgaGUgY2FuIGNhdXNlIG1vcmUgbWFnbmV0cyB0byBqb2luLiBIZSBkZWNpZGVkIHRvIGNyZWF0ZSBhIG1hZ25ldCBleGFjdGx5IEwgdW5pdHMgbG9uZy4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGZsaXAgb3BlcmF0aW9ucyBuZWVkZWQgdG8gZ2V0IGEgbWFnbmV0IG9mIGxlbmd0aCBMLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEwgKDEgJmxlOyBOICZsZTsgNTAwIDAwMCwgMSAmbGU7IEwgJmxlOyBOKSwgdGhlIG51bWJlciBvZiBzdGFydGluZyBtYWduZXRzIGFuZCB0aGUgcmVxdWlyZWQgbGVuZ3RoLiBUaGUgc3RhcnRpbmcgbWFnbmV0cyBhcmUgMSB1bml0IGxvbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgTiBzdHJpbmdzICZxdW90O05TJnF1b3Q7IG9yICZxdW90O1NOJnF1b3Q7LCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gVGhlc2UgYXJlIHRoZSBvcmllbnRhdGlvbnMgb2YgdGhlIG1hZ25ldHMgYWZ0ZXIgTWF0aWphIHB1dHMgdGhlbSBvbiB0aGUgZmxvb3IsIGJ1dCBiZWZvcmUgdGhlIGluaXRpYWwgam9pbmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IGRhdGEgd2lsbCBiZSBzdWNoIHRoYXQgYSBzb2x1dGlvbiB3aWxsIGFsd2F5cyBleGlzdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogaW4gNzAlIG9mIHRoZSBvZmZpY2lhbCB0ZXN0IGRhdGEsIE4gd2lsbCBiZSBsZXNzIHRoYW4gMTAwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBmbGlwcyBuZWVkZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d