시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB165514737.600%

문제

과외맨은 배트맨, 스파이더맨, 슈퍼맨과 같은 슈퍼 히어로를 따라하는 한국의 대표 영웅이다. 오늘은 스파이더맨을 따라해보려고 한다. 과외맨은 고층 건물의 옥상을 점프하면서 돌아다니려고 한다.

고층 건물은 총 N개가 있고, 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 매겨져 있다. 지금 과외맨은 K번 건물 위에 있다. 과외맨은 아직 힘이 많이 부족한다. 따라서, 현재 있는 건물의 왼쪽 또는 오른쪽 건물로만 점프해서 이동할 수 있다. 또, 지금 자신이 있는 건물의 높이보다 높지 않은 빌딩으로만 이동할 수 있다.

이런 과외맨을 도와주고 위해서 상근이는 일부 건물의 옥상에 트램폴린을 설치해 놓았다. 과외맨이 트램폴린을 이용해 점프를 한다면 다른 모든 건물로 이동할 수 있고, 건물의 높이와 상관없이 이동할 수 있다.

과외맨이 방문할 수 있는 서로 다른 건물의 개수의 최댓값을 구하는 프로그램을 작성하시오. 과외맨은 점프를 K번 빌딩에서 시작한다. 같은 건물을 여러 번 방문할 때도, 방문한 건물의 개수는 한 개로 센다. 

입력

첫째 줄에 건물의 수 N과 점프를 시작하는 건물의 번호 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N)

둘째 줄에는 106보다 작은 N개의 정수가 주어진다. 이 정수는 건물의 높이이며, 1번 건물부터 순서대로 주어진다.

셋째 줄에는 '.' 또는 'T'로 이루어진 N개의 문자가 주어진다. i번째 문자가 'T'인 경우에는 i번 건물의 옥상에 트램폴린이 설치되어 있는 것이다.

출력

첫째 줄에 과외맨이 방문할 수 있는 서로 다른 건물 개수의 최댓값을 출력한다.

예제 입력 1

6 4
12 16 16 16 14 14
.T....

예제 출력 1

5

예제 입력 2

10 1
10 7 3 1 1 9 8 2 4 10
..T..T....

예제 출력 2

7
W3sicHJvYmxlbV9pZCI6IjI3OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI3YThcdWQzZjRcdWI5YjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0MCBcdWJjMzBcdWQyYjhcdWI5ZTgsIFx1YzJhNFx1ZDMwY1x1Yzc3NFx1YjM1NFx1YjllOCwgXHVjMjg4XHVkMzdjXHViOWU4XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyODhcdWQzN2MgXHVkNzg4XHVjNWI0XHViODVjXHViOTdjIFx1YjUzMFx1Yjc3Y1x1ZDU1OFx1YjI5NCBcdWQ1NWNcdWFkNmRcdWM3NTggXHViMzAwXHVkNDVjIFx1YzYwMVx1YzZjNVx1Yzc3NFx1YjJlNC4gXHVjNjI0XHViMjk4XHVjNzQwIFx1YzJhNFx1ZDMwY1x1Yzc3NFx1YjM1NFx1YjllOFx1Yzc0NCBcdWI1MzBcdWI3N2NcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVhY2UwXHVjZTM1IFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWM2MjVcdWMwYzFcdWM3NDQgXHVjODEwXHVkNTA0XHVkNTU4XHViYTc0XHVjMTFjIFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJjOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1Y2UzNSBcdWFjNzRcdWJiM2NcdWM3NDAgXHVjZDFkIE5cdWFjMWNcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjOWMwXHVhZTA4IFx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0MCBLXHViYzg4IFx1YWM3NFx1YmIzYyBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVjNTQ0XHVjOWMxIFx1ZDc5OFx1Yzc3NCBcdWI5Y2VcdWM3NzQgXHViZDgwXHVjODcxXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWI2MTBcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWM3NFx1YmIzY1x1Yjg1Y1x1YjljYyBcdWM4MTBcdWQ1MDRcdWQ1NzRcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVjOWMwXHVhZTA4IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YmNmNFx1YjJlNCBcdWIxOTJcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmU0Y1x1YjUyOVx1YzczY1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2YwIFx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0NCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWFjZTAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3N2NcdWJkODAgXHVhYzc0XHViYjNjXHVjNzU4IFx1YzYyNVx1YzBjMVx1YzVkMCBcdWQyYjhcdWI3YThcdWQzZjRcdWI5YjBcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTc0IFx1YjE5M1x1YzU1OFx1YjJlNC4gXHVhY2ZjXHVjNjc4XHViOWU4XHVjNzc0IFx1ZDJiOFx1YjdhOFx1ZDNmNFx1YjliMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWIyZTRcdWI5NzggXHViYWE4XHViNGUwIFx1YWM3NFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWMwYzFcdWFkMDBcdWM1YzZcdWM3NzQgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmY1x1YzY3OFx1YjllOFx1Yzc3NCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVjODEwXHVkNTA0XHViOTdjIEtcdWJjODggXHViZTRjXHViNTI5XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWI1NGNcdWIzYzQsIFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWFjNzRcdWJiM2NcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1ZDU1YyBcdWFjMWNcdWI4NWMgXHVjMTNjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjNzRcdWJiM2NcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVjODEwXHVkNTA0XHViOTdjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWFjNzRcdWJiM2NcdWM3NTggXHViYzg4XHVkNjM4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMDAsMDAwLCAxICZsZTsgSyAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMTA8c3VwPjY8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yzc3NFx1YmE3MCwgMVx1YmM4OCBcdWFjNzRcdWJiM2NcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAmIzM5Oy4mIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTtUJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWFjMDAgJiMzOTtUJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IGlcdWJjODggXHVhYzc0XHViYjNjXHVjNzU4IFx1YzYyNVx1YzBjMVx1YzVkMCBcdWQyYjhcdWI3YThcdWQzZjRcdWI5YjBcdWM3NzQgXHVjMTI0XHVjZTU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NzQgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjNzRcdWJiM2MgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjc5NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRSQU1QT0xJTiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIG1hbnkgYWN0aW9uIHN1cGVyaGVyb2VzIG91dCB0aGVyZTogQmF0bWFuLCBTcGlkZXJtYW4sIFN1cGVybWFuLCBJY2FudHdyaXRlbWFuIGV0Yy4gQW1vbmcgdGhlbSwgdGhlcmUgaXMgb25lIGdlbnRsZW1hbiBjYWxsZWQgS2lja2Fzcy4gVG9kYXkgaGUgd2FudHMgdG8gbWltaWMgU3BpZGVybWFuLCBzbyBoZSBoYXMgY2hvc2VuIGEgcm93IG9mIHRhbGwgc2t5c2NyYXBlcnMgdG8ganVtcCBhcm91bmQgb24uPFwvcD5cclxuXHJcbjxwPlNwZWNpZmljYWxseSwgaGUgaGFzIGNob3NlbiBhIHNlcXVlbmNlIG9mIE4gc2t5c2NyYXBlcnMgbnVtYmVyZWQgMSB0aHJvdWdoIE4gZnJvbSBsZWZ0IHRvIHJpZ2h0LiBIZSBpcyBpbml0aWFsbHkgbG9jYXRlZCBvbiB0aGUgS3RoIHNreXNjcmFwZXIuIFVuZm9ydHVuYXRlbHksIEtpY2thc3MgaGFzIHZlcnkgbGltaXRlZCBwb3dlcnMsIGFuZCBjYW4gdGhlcmVmb3JlIGp1bXAgb25seSB0byB0aGUgYWRqYWNlbnQgc2t5c2NyYXBlciB0byB0aGUgbGVmdCBvciByaWdodCwgYW5kIG9ubHkgaWYgdGhhdCBza3lzY3JhcGVyJiMzOTtzIGhlaWdodCBpcyBub3QgZ3JlYXRlciB0aGFuIHRoZSBoZWlnaHQgb2YgdGhlIHNreXNjcmFwZXIgaGUgaXMgY3VycmVudGx5IG9uLiBIb3dldmVyLCBhbnRpY2lwYXRpbmcgdGhpcyBhbmQgbm90IHdhbnRpbmcgdG8gbG9vayB3ZWFrLCBoZSBoYXMgcG9zaXRpb25lZCB0cmFtcG9saW5lcyBvbiB0b3Agb2Ygc29tZSBza3lzY3JhcGVycywgYW5kIGZyb20gdGhlc2Ugc2t5c2NyYXBlcnMgaGUgY2FuIGp1bXAgb250byBhbnkgb3RoZXIgc2t5c2NyYXBlciwgbm8gbWF0dGVyIGhvdyB0YWxsIG9yIHdoZXJlIHRoYXQgc2t5c2NyYXBlciBpcy48XC9wPlxyXG5cclxuPHA+RmluZCB0aGUgbWF4aW11bSBudW1iZXIgb2YgZGlmZmVyZW50IHNreXNjcmFwZXJzIEtpY2thc3MgY2FuIHZpc2l0IGluIGEgY2hhaW4gb2YganVtcHMgc3RhcnRpbmcgZnJvbSB0aGUgc2t5c2NyYXBlciBudW1iZXJlZCBLLiBJZiBhIHNreXNjcmFwZXIgaXMgdmlzaXRlZCBtb3JlIHRoYW4gb25jZSwgd2Ugc3RpbGwgY291bnQgaXQgb25seSBvbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Nb3Jlb3Zlciwgc2t5c2NyYXBlciBLIGlzIGNvdW50ZWQgZXZlbiBpZiB3ZSBuZXZlciByZXR1cm4gdG8gaXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgdHdvIGludGVnZXJzIE4gYW5kIEsgKDMgJmxlOyBOICZsZTsgMzAwIDAwMCwgMSAmbGU7IEsgJmxlOyBOKSwgdGhlIHRvdGFsIG51bWJlciBvZiBza3lzY3JhcGVycyBhbmQgdGhlIHN0YXJ0aW5nIHNreXNjcmFwZXIsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gaW50ZWdlcnMgbGVzcyB0aGFuIDEwPHN1cD42PFwvc3VwPiwgdGhlIGhlaWdodHMgb2Ygc2t5c2NyYXBlcnMgaW4gb3JkZXIgZnJvbSBsZWZ0IHRvIHJpZ2h0LjxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNlcXVlbmNlIG9mIE4gY2hhcmFjdGVycyAmIzM5Oy4mIzM5OyBvciAmIzM5O1QmIzM5Oy4gSWYgdGhlIGl0aCBjaGFyYWN0ZXIgaXMgJiMzOTtUJiMzOTssIHRoZW4gdGhlcmUgaXMgYSB0cmFtcG9saW5lIHBvc2l0aW9uZWQgb24gdGhlIHRvcCBvZiBza3lzY3JhcGVyIGkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbWF4aW11bSBudW1iZXIgb2YgdmlzaXRlZCBza3lzY3JhcGVycy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlNlY29uZCBzYW1wbGUgZGVzY3JpcHRpb246IHRoZSBzZXF1ZW5jZSBvZiB2aXNpdGVkIHNreXNjcmFwZXJzIGNvdWxkIGJlIHRoZSBmb2xsb3dpbmc6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjEgJnJhcnI7IDIgJnJhcnI7IDMgJnJhcnI7IDYgJnJhcnI7IDEwICZyYXJyOyA5ICZyYXJyOyA4LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==