시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 397 157 137 45.973%

문제

정인이는 강남의 유명한 클럽 Top Root의 도어맨이다. 클럽의 사장은 정인이에게 클럽이 꽉찼을 때, 클럽에 있는 남자와 여자의 수는 거의 비슷해야 한다고 말해주었다.

사람들은 클럽이 문을 열기 전 부터 줄을 서 있는다. 클럽이 문을 열면, 한 명씩 직접 정인이가 입장시켜 준다. 정인이는 그들이 줄을 순서를 바탕으로 입장시켜 준다. 이때, 항상 첫 번째에 있는 사람을 입장시켜야 하는 것은 아니다. 정인이는 재량을 발휘하여 두 번째로 줄 서있는 사람을 첫 번째 사람보다 먼저 입장을 시켜줄 수 있다. 물론 이런 상황이 자주 발생하면 앞 사람이 매우 짜증이 날 것이고, 정인이에게 시비를 걸 수도 있다. 하지만, 정인이는 모든 싸움을 이길 수 있는 사람이기 때문에 이런 걱정은 하지 않아도 된다.

안타깝게도, 정인이는 이렇게 싸움은 잘하지만, 숫자 계산은 잘 하지 못한다. 정인이는 항상 클럽에 들어가있는 남자와 여자의 차이를 머리속에 계산하고 있어야 한다. 이 차이가 정인이가 기억할 수 있는 값보다 크게 된다면 남은 사람들은 클럽에 입장을 할 수 없게 된다.

줄을 서 있는 순서와 정인이가 기억할 수 있는 차이의 최댓값이 주어졌을 때, 클럽에 있는 사람의 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X<100이 주어진다. 둘째 줄에는 줄을 서 있는 순서가 주어진다. W는 여성, M은 남성을 나타내며, 길이는 최대 100이다. 가장 왼쪽에 있는 글자가 줄의 가장 앞에 서 있는 사람의 성별이다. 

출력

클럽에 있는 사람 수의 최댓값을 출력한다.

예제 입력 1

1
MWWMWMMWM

예제 출력 1

9

예제 입력 2

2
WMMMMWWMMMWWMW

예제 출력 2

8
W3sicHJvYmxlbV9pZCI6IjUwMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWM1YjRcdWI5ZTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWFjMTVcdWIwYThcdWM3NTggXHVjNzIwXHViYTg1XHVkNTVjIFx1ZDA3NFx1YjdmZCBUb3AgUm9vdFx1Yzc1OCBcdWIzYzRcdWM1YjRcdWI5ZThcdWM3NzRcdWIyZTQuIFx1ZDA3NFx1YjdmZFx1Yzc1OCBcdWMwYWNcdWM3YTVcdWM3NDAgXHVjODE1XHVjNzc4XHVjNzc0XHVjNWQwXHVhYzhjIFx1ZDA3NFx1YjdmZFx1Yzc3NCBcdWFmNDlcdWNjM2NcdWM3NDQgXHViNTRjLCBcdWQwNzRcdWI3ZmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWM1ZWNcdWM3OTBcdWM3NTggXHVjMjE4XHViMjk0IFx1YWM3MFx1Yzc1OCBcdWJlNDRcdWMyYjdcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0XHVhY2UwIFx1YjlkMFx1ZDU3NFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1ZDA3NFx1YjdmZFx1Yzc3NCBcdWJiMzhcdWM3NDQgXHVjNWY0XHVhZTMwIFx1YzgwNCBcdWJkODBcdWQxMzAgXHVjOTA0XHVjNzQ0IFx1YzExYyBcdWM3ODhcdWIyOTRcdWIyZTQuIFx1ZDA3NFx1YjdmZFx1Yzc3NCBcdWJiMzhcdWM3NDQgXHVjNWY0XHViYTc0LCBcdWQ1NWMgXHViYTg1XHVjNTI5IFx1YzljMVx1YzgxMSBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjNzg1XHVjN2E1XHVjMmRjXHVjZjFjIFx1YzkwMFx1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWM5MDRcdWM3NDQgXHVjMjFjXHVjMTFjXHViOTdjIFx1YmMxNFx1ZDBkNVx1YzczY1x1Yjg1YyZuYnNwO1x1Yzc4NVx1YzdhNVx1YzJkY1x1Y2YxYyBcdWM5MDBcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVkNTZkXHVjMGMxIFx1Y2NhYiBcdWJjODhcdWM5ZjhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWM3ODVcdWM3YTVcdWMyZGNcdWNmMWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM3YWNcdWI3YzlcdWM3NDQgXHViYzFjXHVkNzE4XHVkNTU4XHVjNWVjIFx1YjQ1MCBcdWJjODhcdWM5ZjhcdWI4NWMgXHVjOTA0IFx1YzExY1x1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWJjZjRcdWIyZTQgXHViYTNjXHVjODAwIFx1Yzc4NVx1YzdhNVx1Yzc0NCBcdWMyZGNcdWNmMWNcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYjNjXHViODYwIFx1Yzc3NFx1YjdmMCBcdWMwYzFcdWQ2NjlcdWM3NzQgXHVjNzkwXHVjOGZjIFx1YmMxY1x1YzBkZFx1ZDU1OFx1YmE3NCBcdWM1NWUgXHVjMGFjXHViNzhjXHVjNzc0IFx1YjllNFx1YzZiMCBcdWM5ZGNcdWM5OWRcdWM3NzQgXHViMGEwIFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVjODE1XHVjNzc4XHVjNzc0XHVjNWQwXHVhYzhjIFx1YzJkY1x1YmU0NFx1Yjk3YyBcdWFjNzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzJmOFx1YzZjMFx1Yzc0NCBcdWM3NzRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzc3NFx1YjdmMCBcdWFjNzFcdWM4MTVcdWM3NDAgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0OFx1ZDBjMFx1YWU1ZFx1YWM4Y1x1YjNjNCwgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMyZjhcdWM2YzBcdWM3NDAgXHVjNzk4XHVkNTU4XHVjOWMwXHViOWNjLCBcdWMyMmJcdWM3OTAgXHVhY2M0XHVjMGIwXHVjNzQwIFx1Yzc5OCBcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LiBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxIFx1ZDA3NFx1YjdmZFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWM3ODhcdWIyOTQgXHViMGE4XHVjNzkwXHVjNjQwIFx1YzVlY1x1Yzc5MFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWI5N2MgXHViYTM4XHViOWFjXHVjMThkXHVjNWQwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjYzI4XHVjNzc0XHVhYzAwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWFlMzBcdWM1YjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMTJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzhjIFx1YjQxY1x1YjJlNFx1YmE3NCBcdWIwYThcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1ZDA3NFx1YjdmZFx1YzVkMCBcdWM3ODVcdWM3YTVcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDRcdWM3NDQgXHVjMTFjIFx1Yzc4OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YWUzMFx1YzViNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMDc0XHViN2ZkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YWUzMFx1YzViNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjYzI4XHVjNzc0IFgmbHQ7MTAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5MDRcdWM3NDQgXHVjMTFjIFx1Yzc4OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBXXHViMjk0IFx1YzVlY1x1YzEzMSwgTVx1Yzc0MCBcdWIwYThcdWMxMzFcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMFx1Yzc3NFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzkwNFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjNWQwIFx1YzExYyBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzEzMVx1YmNjNFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQwNzRcdWI3ZmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4YyBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRG9vcm1hbiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGRvb3JtYW4gQnJ1bm8gYXQgdGhlIHBvcHVsYXIgbmlnaHQgY2x1YiBIZWF2ZW4gaXMgaGF2aW5nIGEgaGFyZCB0aW1lIGZ1bGZpbGxpbmcgaGlzIGR1dGllcy4gSGUgd2FzIHRvbGQgYnkgdGhlIG93bmVyIHRoYXQgd2hlbiB0aGUgY2x1YiBpcyBmdWxsLCB0aGUgbnVtYmVyIG9mIHdvbWVuIGFuZCBtZW4gbGV0IGludG8gdGhlIGNsdWIgc2hvdWxkIGJlIHJvdWdobHkgdGhlIHNhbWUuIFdoZW4gdGhlIG5pZ2h0IGNsdWIgb3BlbnMsIHBlb3BsZSB3YW50aW5nIHRvIGVudGVyIHRoZSBjbHViIGFyZSBhbHJlYWR5IGxpbmVkIHVwIGluIGEgcXVldWUsIGFuZCBCcnVubyBjYW4gb25seSBsZXQgdGhlbSBpbiBvbmUtYnktb25lLiBIZSBsZXRzIHRoZW0gaW4gbW9yZW9yLWxlc3MgaW4gdGhlIG9yZGVyIHRoZXkgYXJlIGxpbmVkIHVwLiBIZSBjYW4gaG93ZXZlciBkZWNpZGUgdG8gbGV0IHRoZSBzZWNvbmQgcGVyc29uIGluIHRoZSBxdWV1ZSBjdXQgdGhlIGxpbmUgYW5kIHNsaXAgaW50byB0aGUgY2x1YiBiZWZvcmUgdGhlIHBlcnNvbiBpbiBmcm9udC4gVGhpcyB3aWxsIG5vIGRvdWJ0IHVwc2V0IHRoZSBwZXJzb24gZmlyc3QgaW4gbGluZSwgZXNwZWNpYWxseSB3aGVuIHRoaXMgaGFwcGVucyBtdWx0aXBsZSB0aW1lcywgYnV0IEJydW5vIGlzIHF1aXRlIGEgYmlnIGd1eSBhbmQgaXMgY2FwYWJsZSBvZiBoYW5kbGluZyB0cm91YmxlbWFrZXJzLiBVbmZvcnR1bmF0ZWx5IHRob3VnaCwgaGUgaXMgbm90IHRoYXQgc3Ryb25nIG9uIG1lbnRhbCBjYWxjdWxhdGlvbnMgdW5kZXIgdGhlc2UgY2lyY3Vtc3RhbmNlcy4gSGUgZmluZHMga2VlcGluZyB0cmFjayBvZiB0aGUgZGlmZmVyZW5jZSBvZiB0aGUgbnVtYmVyIG9mIHdvbWVuIGFuZCBudW1iZXIgb2YgbWVuIGxldCBpbnRvIHRoZSBjbHViIGEgY2hhbGxlbmdpbmcgdGFzay4gQXMgc29vbiBhcyB0aGUgYWJzb2x1dGUgZGlmZmVyZW5jZSBnZXRzIHRvbyBiaWcsIGhlIGxvb3NlcyB0cmFjayBvZiBoaXMgY291bnRpbmcgYW5kIG11c3QgZGVjbGFyZSB0byB0aGUgcGFydHkgcGVvcGxlIHJlbWFpbmluZyBpbiB0aGUgcXVldWUgdGhhdCB0aGUgY2x1YiBpcyBmdWxsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBYICZsdDsgMTAwIGRlc2NyaWJpbmcgdGhlIGxhcmdlc3QgYWJzb2x1dGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBudW1iZXIgb2Ygd29tZW4gYW5kIG51bWJlciBvZiBtZW4gbGV0IGludG8gdGhlIGNsdWIsIHRoYXQgQnJ1bm8gY2FuIGhhbmRsZS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGEgc3RyaW5nIGNvbnNpc3Rpbmcgc29sZWx5IG9mIHRoZSBjaGFyYWN0ZXJzICZyc3F1bztXJnJzcXVvOyBhbmQgJnJzcXVvO00mcnNxdW87IG9mIGxlbmd0aCBhdCBtb3N0IDEwMCwgZGVzY3JpYmluZyB0aGUgZ2VuZGVycyBvZiB0aGUgcGVvcGxlIGluIHRoZSBxdWV1ZSwgaW4gb3JkZXIuIFRoZSBsZWZ0bW9zdCBjaGFyYWN0ZXIgb2YgdGhlIHN0cmluZyBpcyB0aGUgZ2VuZGVyIG9mIHRoZSBwZXJzb24gXHVmYjAxcnN0IGluIGxpbmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG1heGltdW0gbnVtYmVyIG9mIHBlb3BsZSBCcnVubyBjYW4gbGV0IGludG8gdGhlIGNsdWIgd2l0aG91dCBsb29zaW5nIHRyYWNrIG9mIGhpcyBjb3VudGluZy4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGUgY2x1YiBpcyBsYXJnZSBlbm91Z2ggdG8gaG9sZCBhbGwgdGhlIHBlb3BsZSBpbiB0aGUgcXVldWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d