시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 386 150 134 45.734%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

1
MWWMWMMWM

예제 출력 1

9

예제 입력 2

2
WMMMMWWMMMWWMW

예제 출력 2

8
W3sicHJvYmxlbV9pZCI6IjUwMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWM1YjRcdWI5ZTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWFjMTVcdWIwYThcdWM3NTggXHVjNzIwXHViYTg1XHVkNTVjIFx1ZDA3NFx1YjdmZCBUb3AgUm9vdFx1Yzc1OCBcdWIzYzRcdWM1YjRcdWI5ZThcdWM3NzRcdWIyZTQuIFx1ZDA3NFx1YjdmZFx1Yzc1OCBcdWMwYWNcdWM3YTVcdWM3NDAgXHVjODE1XHVjNzc4XHVjNzc0XHVjNWQwXHVhYzhjIFx1ZDA3NFx1YjdmZFx1Yzc3NCBcdWFmNDlcdWNjM2NcdWM3NDQgXHViNTRjLCBcdWQwNzRcdWI3ZmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWM1ZWNcdWM3OTBcdWM3NTggXHVjMjE4XHViMjk0IFx1YWM3MFx1Yzc1OCBcdWJlNDRcdWMyYjdcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0XHVhY2UwIFx1YjlkMFx1ZDU3NFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1ZDA3NFx1YjdmZFx1Yzc3NCBcdWJiMzhcdWM3NDQgXHVjNWY0XHVhZTMwIFx1YzgwNCBcdWJkODBcdWQxMzAgXHVjOTA0XHVjNzQ0IFx1YzExYyBcdWM3ODhcdWIyOTRcdWIyZTQuIFx1ZDA3NFx1YjdmZFx1Yzc3NCBcdWJiMzhcdWM3NDQgXHVjNWY0XHViYTc0LCBcdWQ1NWMgXHViYTg1XHVjNTI5IFx1YzljMVx1YzgxMSBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjNzg1XHVjN2E1XHVjMmRjXHVjZjFjIFx1YzkwMFx1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWM5MDRcdWM3NDQgXHVjMjFjXHVjMTFjXHViOTdjIFx1YmMxNFx1ZDBkNVx1YzczY1x1Yjg1YyZuYnNwO1x1Yzc4NVx1YzdhNVx1YzJkY1x1Y2YxYyBcdWM5MDBcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1ZDU2ZFx1YzBjMSBcdWNjYWIgXHViYzg4XHVjOWY4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDQgXHVjNzg1XHVjN2E1XHVjMmRjXHVjZjFjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjN2FjXHViN2M5XHVjNzQ0IFx1YmMxY1x1ZDcxOFx1ZDU1OFx1YzVlYyBcdWI0NTAgXHViYzg4XHVjOWY4XHViODVjIFx1YzkwNCBcdWMxMWNcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQ0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMGFjXHViNzhjXHViY2Y0XHViMmU0IFx1YmEzY1x1YzgwMCBcdWM3ODVcdWM3YTVcdWM3NDQgXHVjMmRjXHVjZjFjXHVjOTA0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWM3NzRcdWI3ZjAgXHVjMGMxXHVkNjY5XHVjNzc0IFx1Yzc5MFx1YzhmYyBcdWJjMWNcdWMwZGRcdWQ1NThcdWJhNzQgXHVjNTVlIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVjOWRjXHVjOTlkXHVjNzc0IFx1YjBhMCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWMyZGNcdWJlNDRcdWI5N2MgXHVhYzc4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyZjhcdWM2YzBcdWM3NDQgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM3NzRcdWI3ZjAgXHVhYzcxXHVjODE1XHVjNzQwIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQsIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjMmY4XHVjNmMwXHVjNzQwIFx1Yzc5OFx1ZDU1OFx1YzljMFx1YjljYywgXHVjMjJiXHVjNzkwIFx1YWNjNFx1YzBiMFx1Yzc0MCBcdWM3OTggXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQwNzRcdWI3ZmRcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHVjNzg4XHViMjk0IFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWM1ZWNcdWM3OTBcdWM3NTggXHVjYzI4XHVjNzc0XHViOTdjIFx1YmEzOFx1YjlhY1x1YzE4ZFx1YzVkMCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1Y2MyOFx1Yzc3NFx1YWMwMCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVhZTMwXHVjNWI1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzEyXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM4YyBcdWI0MWNcdWIyZTRcdWJhNzQgXHViMGE4XHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWQwNzRcdWI3ZmRcdWM1ZDAgXHVjNzg1XHVjN2E1XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTA0XHVjNzQ0IFx1YzExYyBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHVjNjQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWFlMzBcdWM1YjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDA3NFx1YjdmZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWFlMzBcdWM1YjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1Y2MyOFx1Yzc3NCBYJmx0OzEwMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOTA0XHVjNzQ0IFx1YzExYyBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gV1x1YjI5NCBcdWM1ZWNcdWMxMzEsIE1cdWM3NDAgXHViMGE4XHVjMTMxXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWM3NzRcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM5MDRcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzVkMCBcdWMxMWMgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMxMzFcdWJjYzRcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMDc0XHViN2ZkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGMgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTAwMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRvb3JtYW4iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBkb29ybWFuIEJydW5vIGF0IHRoZSBwb3B1bGFyIG5pZ2h0IGNsdWIgSGVhdmVuIGlzIGhhdmluZyBhIGhhcmQgdGltZSBmdWxmaWxsaW5nIGhpcyBkdXRpZXMuIEhlIHdhcyB0b2xkIGJ5IHRoZSBvd25lciB0aGF0IHdoZW4gdGhlIGNsdWIgaXMgZnVsbCwgdGhlIG51bWJlciBvZiB3b21lbiBhbmQgbWVuIGxldCBpbnRvIHRoZSBjbHViIHNob3VsZCBiZSByb3VnaGx5IHRoZSBzYW1lLiBXaGVuIHRoZSBuaWdodCBjbHViIG9wZW5zLCBwZW9wbGUgd2FudGluZyB0byBlbnRlciB0aGUgY2x1YiBhcmUgYWxyZWFkeSBsaW5lZCB1cCBpbiBhIHF1ZXVlLCBhbmQgQnJ1bm8gY2FuIG9ubHkgbGV0IHRoZW0gaW4gb25lLWJ5LW9uZS4gSGUgbGV0cyB0aGVtIGluIG1vcmVvci1sZXNzIGluIHRoZSBvcmRlciB0aGV5IGFyZSBsaW5lZCB1cC4gSGUgY2FuIGhvd2V2ZXIgZGVjaWRlIHRvIGxldCB0aGUgc2Vjb25kIHBlcnNvbiBpbiB0aGUgcXVldWUgY3V0IHRoZSBsaW5lIGFuZCBzbGlwIGludG8gdGhlIGNsdWIgYmVmb3JlIHRoZSBwZXJzb24gaW4gZnJvbnQuIFRoaXMgd2lsbCBubyBkb3VidCB1cHNldCB0aGUgcGVyc29uIGZpcnN0IGluIGxpbmUsIGVzcGVjaWFsbHkgd2hlbiB0aGlzIGhhcHBlbnMgbXVsdGlwbGUgdGltZXMsIGJ1dCBCcnVubyBpcyBxdWl0ZSBhIGJpZyBndXkgYW5kIGlzIGNhcGFibGUgb2YgaGFuZGxpbmcgdHJvdWJsZW1ha2Vycy4gVW5mb3J0dW5hdGVseSB0aG91Z2gsIGhlIGlzIG5vdCB0aGF0IHN0cm9uZyBvbiBtZW50YWwgY2FsY3VsYXRpb25zIHVuZGVyIHRoZXNlIGNpcmN1bXN0YW5jZXMuIEhlIGZpbmRzIGtlZXBpbmcgdHJhY2sgb2YgdGhlIGRpZmZlcmVuY2Ugb2YgdGhlIG51bWJlciBvZiB3b21lbiBhbmQgbnVtYmVyIG9mIG1lbiBsZXQgaW50byB0aGUgY2x1YiBhIGNoYWxsZW5naW5nIHRhc2suIEFzIHNvb24gYXMgdGhlIGFic29sdXRlIGRpZmZlcmVuY2UgZ2V0cyB0b28gYmlnLCBoZSBsb29zZXMgdHJhY2sgb2YgaGlzIGNvdW50aW5nIGFuZCBtdXN0IGRlY2xhcmUgdG8gdGhlIHBhcnR5IHBlb3BsZSByZW1haW5pbmcgaW4gdGhlIHF1ZXVlIHRoYXQgdGhlIGNsdWIgaXMgZnVsbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgWCAmbHQ7IDEwMCBkZXNjcmliaW5nIHRoZSBsYXJnZXN0IGFic29sdXRlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgbnVtYmVyIG9mIHdvbWVuIGFuZCBudW1iZXIgb2YgbWVuIGxldCBpbnRvIHRoZSBjbHViLCB0aGF0IEJydW5vIGNhbiBoYW5kbGUuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHN0cmluZyBjb25zaXN0aW5nIHNvbGVseSBvZiB0aGUgY2hhcmFjdGVycyAmcnNxdW87VyZyc3F1bzsgYW5kICZyc3F1bztNJnJzcXVvOyBvZiBsZW5ndGggYXQgbW9zdCAxMDAsIGRlc2NyaWJpbmcgdGhlIGdlbmRlcnMgb2YgdGhlIHBlb3BsZSBpbiB0aGUgcXVldWUsIGluIG9yZGVyLiBUaGUgbGVmdG1vc3QgY2hhcmFjdGVyIG9mIHRoZSBzdHJpbmcgaXMgdGhlIGdlbmRlciBvZiB0aGUgcGVyc29uIFx1ZmIwMXJzdCBpbiBsaW5lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBtYXhpbXVtIG51bWJlciBvZiBwZW9wbGUgQnJ1bm8gY2FuIGxldCBpbnRvIHRoZSBjbHViIHdpdGhvdXQgbG9vc2luZyB0cmFjayBvZiBoaXMgY291bnRpbmcuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGNsdWIgaXMgbGFyZ2UgZW5vdWdoIHRvIGhvbGQgYWxsIHRoZSBwZW9wbGUgaW4gdGhlIHF1ZXVlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==