시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 170 42 37 26.619%

문제

IOI 국가는 최근 새로운 열차 노선인 IOI선을 개통했다.

IOI 열차는 한 칸짜리 단위 열차 여러 대가 연결된 모습을 하고 있으며 단위 열차의 종류는 I 또는 O이다.

안전을 위해 IOI 열차의 인접한 칸은 서로 다른 종류여야 하며, 운전석은 I칸에만 있기 때문에 열차의 양 끝 칸은 항상 I여야 한다.

예를 들어 OIOI나 IOOI와 같은 열차는 불가능하다.

열차는 각 차량의 종류를 나타낸 문자를 순서대로 이어 붙인 문자열로 나타낼 수 있으며 문자열의 길이가 곧 열차의 길이이다.

예를 들어 열차 IOIOI의 길이는 5이며 열차 I는 길이 1의 열차가 된다.

이제 IOI선의 개통 전날이다.

역사적인 첫 운행을 맡게 된 차장 승택이는 가능한 한 많은 승객을 태울 수 있도록 현재 보관 중인 단위 열차들을 이어 붙여 한 대의 긴 IOI 열차를 만드려고 한다.

현재 단위 열차 I 또는 O 여러 대가 두 차고지에 일렬로 주차되어 있다.

두 차고지 중 어디서 열차를 꺼낼 지는 자유지만, 열차를 들어서 옮길 수는 없기 때문에 차고의 입구에 가까운 열차부터 차례차례 꺼낼 수밖에 없다.

단, 열차 편성이 시작되기 전에 각 차고지에서 원하는 만큼씩 열차를 미리 외부 차고로 보내둘 수가 있다.

한 번 외부 차고로 보낸 열차칸은 열차를 편성할 때 사용할 수 없다.

또한 한 번 열차 편성이 시작된 다음엔 외부 차고로 열차를 보낼 수 없다.


위는 예제 입력에 대응하는 그림이다. 열차 편성이 시작되면 더 이상 외부 차고를 이용할 수가 없으며,

외부 차고의 열차는 열차 편성에 이용할 수가 없다.

승택이는 적절히 차량 대기소로 열차를 보낸 뒤 규칙에 맞게 열차를 이어붙여 한 대의 긴 IOI 열차를 만들 것이다.

이때 얼마나 긴 열차를 만들 수 있을까?

입력

첫 줄에 차고 S에 저장된 열차의 수 N, 차고 T에 주차된 열차의 수 M이 주어진다. (1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000)

두 번째 줄에 차고 S에 저장된 열차들이 문자열 한 줄로 주어진다.

세 번째 줄에 차고 T에 저장된 열차들이 문자열 한 줄로 주어진다.

문자열의 첫 글자가 차고의 입구 쪽에 주차된 열차이다.

출력

첫 줄에 가장 긴 열차의 길이를 출력한다.

열차를 만들 수 없다면 0을 출력한다.

예제 입력 1

5 5
OIOOI
OOIOI

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjU1MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZWNcdWI4MjRcdWI3N2MgSU9JIFx1YzVmNFx1Y2MyOCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0SU9JIFx1YWQ2ZFx1YWMwMFx1YjI5NCBcdWNkNWNcdWFkZmMgXHVjMGM4XHViODVjXHVjNmI0IFx1YzVmNFx1Y2MyOCBcdWIxNzhcdWMxMjBcdWM3NzggSU9JXHVjMTIwXHVjNzQ0IFx1YWMxY1x1ZDFiNVx1ZDU4OFx1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0SU9JIFx1YzVmNFx1Y2MyOFx1YjI5NCBcdWQ1NWMgXHVjZTc4XHVjOWRjXHViOWFjIFx1YjJlOFx1YzcwNCBcdWM1ZjRcdWNjMjggXHVjNWVjXHViN2VjIFx1YjMwMFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViYWE4XHVjMmI1XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAgXHViMmU4XHVjNzA0IFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWM4ODVcdWI5NThcdWIyOTQgSSBcdWI2MTBcdWIyOTQgT1x1Yzc3NFx1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0XHVjNTQ4XHVjODA0XHVjNzQ0IFx1YzcwNFx1ZDU3NCBJT0kgXHVjNWY0XHVjYzI4XHVjNzU4IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4ODVcdWI5NThcdWM1ZWNcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWM2YjRcdWM4MDRcdWMxMWRcdWM3NDAgSVx1Y2U3OFx1YzVkMFx1YjljYyBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWM1OTEgXHViMDVkIFx1Y2U3OFx1Yzc0MCBcdWQ1NmRcdWMwYzEgSVx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuXHJcbjxcL3A+XHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgT0lPSVx1YjA5OCBJT09JXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM1ZjRcdWNjMjhcdWIyOTQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWM1ZjRcdWNjMjhcdWIyOTQgXHVhYzAxIFx1Y2MyOFx1YjdjOVx1Yzc1OCBcdWM4ODVcdWI5NThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjZTcgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM1ZjRcdWNjMjggSU9JT0lcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDVcdWM3NzRcdWJhNzAgXHVjNWY0XHVjYzI4IElcdWIyOTQgXHVhZTM4XHVjNzc0IDFcdWM3NTggXHVjNWY0XHVjYzI4XHVhYzAwIFx1YjQxY1x1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0XHVjNzc0XHVjODFjIElPSVx1YzEyMFx1Yzc1OCBcdWFjMWNcdWQxYjUgXHVjODA0XHViMGEwXHVjNzc0XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWM1ZWRcdWMwYWNcdWM4MDFcdWM3NzggXHVjY2FiIFx1YzZiNFx1ZDU4OVx1Yzc0NCBcdWI5ZTFcdWFjOGMgXHViNDFjIFx1Y2MyOFx1YzdhNSBcdWMyYjlcdWQwZGRcdWM3NzRcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjMmI5XHVhYzFkXHVjNzQ0IFx1ZDBkY1x1YzZiOCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1ZDYwNFx1YzdhYyBcdWJjZjRcdWFkMDAgXHVjOTExXHVjNzc4IFx1YjJlOFx1YzcwNCBcdWM1ZjRcdWNjMjhcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1YzVlYyBcdWQ1NWMgXHViMzAwXHVjNzU4IFx1YWUzNCBJT0kgXHVjNWY0XHVjYzI4XHViOTdjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuXHJcbjxcL3A+XHJcbjxwPlxyXG5cdFx1ZDYwNFx1YzdhYyBcdWIyZThcdWM3MDQgXHVjNWY0XHVjYzI4IEkgXHViNjEwXHViMjk0IE8gXHVjNWVjXHViN2VjIFx1YjMwMFx1YWMwMCBcdWI0NTAgXHVjYzI4XHVhY2UwXHVjOWMwXHVjNWQwIFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWM4ZmNcdWNjMjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWI0NTAgXHVjYzI4XHVhY2UwXHVjOWMwIFx1YzkxMSBcdWM1YjRcdWI1MTRcdWMxMWMgXHVjNWY0XHVjYzI4XHViOTdjIFx1YWViY1x1YjBiYyBcdWM5YzBcdWIyOTQgXHVjNzkwXHVjNzIwXHVjOWMwXHViOWNjLCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHViNGU0XHVjNWI0XHVjMTFjIFx1YzYyZVx1YWUzOCBcdWMyMThcdWIyOTQgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNjMjhcdWFjZTBcdWM3NTggXHVjNzg1XHVhZDZjXHVjNWQwIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWM1ZjRcdWNjMjhcdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHVjYzI4XHViODQwIFx1YWViY1x1YjBiYyBcdWMyMThcdWJjMTZcdWM1ZDAgXHVjNWM2XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWIyZTgsIFx1YzVmNFx1Y2MyOCBcdWQzYjhcdWMxMzFcdWM3NzQgXHVjMmRjXHVjNzkxXHViNDE4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWFjMDEgXHVjYzI4XHVhY2UwXHVjOWMwXHVjNWQwXHVjMTFjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2NcdWM1MjkgXHVjNWY0XHVjYzI4XHViOTdjIFx1YmJmOFx1YjlhYyBcdWM2NzhcdWJkODAgXHVjYzI4XHVhY2UwXHViODVjIFx1YmNmNFx1YjBiNFx1YjQ1OCBcdWMyMThcdWFjMDAgXHVjNzg4XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWQ1NWMgXHViYzg4IFx1YzY3OFx1YmQ4MCBcdWNjMjhcdWFjZTBcdWI4NWMgXHViY2Y0XHViMGI4IFx1YzVmNFx1Y2MyOFx1Y2U3OFx1Yzc0MCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVkM2I4XHVjMTMxXHVkNTYwIFx1YjU0YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0XHViNjEwXHVkNTVjIFx1ZDU1YyBcdWJjODggXHVjNWY0XHVjYzI4IFx1ZDNiOFx1YzEzMVx1Yzc3NCBcdWMyZGNcdWM3OTFcdWI0MWMgXHViMmU0XHVjNzRjXHVjNWQ0IFx1YzY3OFx1YmQ4MCBcdWNjMjhcdWFjZTBcdWI4NWMgXHVjNWY0XHVjYzI4XHViOTdjIFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNWM2XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHQ8aW1nIHNyYz1cIlwvdXNlcnVwbG9hZFwvcG9ydGFibGVhbmdlbFwvMjAxNTAzXC9mYTIxNDY4MWFiMDY2N2NlOTg4NmRjNDAwN2QwOWY4MC5wbmdcIj48c3Bhbj48XC9zcGFuPjxicj5cclxuPFwvcD5cclxuPHA+XHJcblx0XHVjNzA0XHViMjk0IFx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVjNzUxXHVkNTU4XHViMjk0IFx1YWRmOFx1YjliY1x1Yzc3NFx1YjJlNC4gXHVjNWY0XHVjYzI4IFx1ZDNiOFx1YzEzMVx1Yzc3NCBcdWMyZGNcdWM3OTFcdWI0MThcdWJhNzQgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM2NzhcdWJkODAgXHVjYzI4XHVhY2UwXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHVjNzNjXHViYTcwLFxyXG48XC9wPlxyXG48cD5cclxuXHRcdWM2NzhcdWJkODAgXHVjYzI4XHVhY2UwXHVjNzU4IFx1YzVmNFx1Y2MyOFx1YjI5NCBcdWM1ZjRcdWNjMjggXHVkM2I4XHVjMTMxXHVjNWQwIFx1Yzc3NFx1YzZhOVx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWMyYjlcdWQwZGRcdWM3NzRcdWIyOTQgXHVjODAxXHVjODA4XHVkNzg4IFx1Y2MyOFx1YjdjOSBcdWIzMDBcdWFlMzBcdWMxOGNcdWI4NWMgXHVjNWY0XHVjYzI4XHViOTdjIFx1YmNmNFx1YjBiOCBcdWI0YTQgXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVjNzc0XHVjNWI0XHViZDk5XHVjNWVjIFx1ZDU1YyBcdWIzMDBcdWM3NTggXHVhZTM0IElPSSBcdWM1ZjRcdWNjMjhcdWI5N2MgXHViOWNjXHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0XHVjNzc0XHViNTRjIFx1YzViY1x1YjljOFx1YjA5OCBcdWFlMzQgXHVjNWY0XHVjYzI4XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjP1xyXG48XC9wPiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWNjMjhcdWFjZTAgU1x1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MWMgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzIxOCBOLCBcdWNjMjhcdWFjZTAgVFx1YzVkMCBcdWM4ZmNcdWNjMjhcdWI0MWMgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgXHUyMjY0IE4gXHUyMjY0IDIwMDAsIDEgXHUyMjY0IE0gXHUyMjY0IDIwMDApXHJcbjxcL3A+XHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2MyOFx1YWNlMCBTXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWM1ZjRcdWNjMjhcdWI0ZTRcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjMjhcdWFjZTAgVFx1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MWMgXHVjNWY0XHVjYzI4XHViNGU0XHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1Y2NhYiBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjYzI4XHVhY2UwXHVjNzU4IFx1Yzc4NVx1YWQ2YyBcdWNhYmRcdWM1ZDAgXHVjOGZjXHVjYzI4XHViNDFjIFx1YzVmNFx1Y2MyOFx1Yzc3NFx1YjJlNC5cclxuPFwvcD4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuXHJcbjxcL3A+XHJcbjxwPlxyXG5cdFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC5cclxuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTI4IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSU9JIFx1NTIxN1x1OGVjYVx1MzA2N1x1ODg0Y1x1MzA1M1x1MzA0NiIsImRlc2NyaXB0aW9uIjoiPHA+SU9JIFx1NTZmZFx1MzA2N1x1MzA2Zlx1MzA1M1x1MzA2ZVx1MzA1Zlx1MzA3M1x1NjViMFx1MzA1Zlx1MzA2Ylx1OTI0NFx1OTA1M1x1MzA5Mlx1NjU3N1x1OGEyZFx1MzA1N1x1MzA1Zlx1ZmYwZUlPSSBcdTU2ZmRcdTMwNmVcdTkyNDRcdTkwNTNcdTMwOTJcdThkNzBcdTMwOGJcdTUyMTdcdThlY2FcdTMwNmZcdTMwNDRcdTMwNGZcdTMwNjRcdTMwNGJcdTMwNmVcdThlY2FcdTRlMjFcdTMwNGNcdTkwMjNcdTdkNTBcdTMwNTVcdTMwOGNcdTMwNWZcdTMwODJcdTMwNmVcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdThlY2FcdTRlMjFcdTMwNmJcdTMwNmYgSSwgTyBcdTMwNmUgMiBcdTdhMmVcdTk4NWVcdTMwNGNcdTMwNDJcdTMwOGJcdWZmMGVcdThlY2FcdTRlMjFcdTMwNmZcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTc1NzBcdTMwNmFcdTMwOGJcdTdhMmVcdTk4NWVcdTMwNmVcdThlY2FcdTRlMjFcdTMwNjhcdTMwNTdcdTMwNGJcdTkwMjNcdTdkNTBcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdWZmMGVcdTMwN2VcdTMwNWZcdWZmMGNcdTUyMTdcdThlY2FcdTMwNmJcdTkwNGJcdThlZTJcdTVlMmRcdTMwOTJcdThhMmRcdTMwNTFcdTMwOGJcdTk1YTJcdTRmYzJcdTRlMGFcdWZmMGNcdTUyMTdcdThlY2FcdTMwNmVcdTRlMjFcdTdhZWZcdTMwNmVcdThlY2FcdTRlMjFcdTMwNmZcdTdhMmVcdTk4NWUgSSBcdTMwNjdcdTMwNmFcdTMwNTFcdTMwOGNcdTMwNzBcdTMwNmFcdTMwODlcdTMwNmFcdTMwNDRcdWZmMGVcdTUyMTdcdThlY2FcdTMwNmZcdThlY2FcdTRlMjFcdTMwNmVcdTdhMmVcdTk4NWVcdTMwOTJcdTg4NjhcdTMwNTlcdTY1ODdcdTViNTdcdTMwOTJcdTk4MDZcdTMwNmJcdTMwNjRcdTMwNmFcdTMwNTJcdTMwNWZcdTY1ODdcdTViNTdcdTUyMTdcdTMwNjdcdTg4NjhcdTMwNTVcdTMwOGNcdWZmMGNcdTUyMTdcdThlY2FcdTMwNmVcdTk1NzdcdTMwNTVcdTMwNmZcdTMwNWRcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmVcdTk1NzdcdTMwNTVcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNjhcdTMwNTlcdTMwOGJcdWZmMGVcdTMwNWZcdTMwNjhcdTMwNDhcdTMwNzBcdWZmMGMgSU9JT0kgXHUzMDZlXHU5ODA2XHUzMDZiXHU4ZWNhXHU0ZTIxXHUzMDkyXHU5MDIzXHU3ZDUwXHUzMDU5XHUzMDhiXHUzMDY4XHU5NTc3XHUzMDU1IDUgXHUzMDZlXHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDY3XHUzMDRkXHVmZjBjXHUzMDdlXHUzMDVmXHU4ZWNhXHU0ZTIxIEkgXHUzMDZmXHU1MzU4XHU3MmVjXHUzMDY3XHU5NTc3XHUzMDU1IDEgXHUzMDZlXHU1MjE3XHU4ZWNhXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHU4ZWNhXHU0ZTIxXHUzMDkyIE9JT0kgXHUzMDg0SU9PSSBcdTMwNjhcdTMwNDRcdTMwNjNcdTMwNWZcdTk4MDZcdTMwNmJcdTRlMjZcdTMwNzlcdTMwNjZcdTMwODJcdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNTlcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU4ZWNhXHU0ZTIxXHUzMDRjIDIgXHUzMDY0XHUzMDZlXHU4ZWNhXHU1ZWFiXHUzMDZiXHU2ODNjXHU3ZDBkXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHUzMDZlXHU4ZWNhXHU1ZWFiXHUzMDZlXHU0ZTJkXHUzMDZiXHUzMDZmXHU4ZWNhXHU0ZTIxXHUzMDRjXHU0ZTAwXHU1MjE3XHUzMDZiXHU0ZTI2XHUzMDkzXHUzMDY3XHUzMDQ0XHUzMDhiXHVmZjBlXHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU5XHUzMDhiXHUzMDY4XHUzMDRkXHUzMDZmXHU4ZWNhXHU1ZWFiXHUzMDRiXHUzMDg5XHU4ZWNhXHU0ZTIxXHUzMDkyXHU1MWZhXHUzMDU3XHUzMDY2XHUzMDRkXHUzMDY2XHU4ZWNhXHU1ZWFiXHU1MjRkXHUzMDY3XHU5MDIzXHU3ZDUwXHUzMDU3XHUzMDY2XHUzMDQ0XHUzMDRmXHVmZjBlXHU4ZWNhXHU1ZWFiXHUzMDRiXHUzMDg5XHU1MWZhXHUzMDViXHUzMDhiXHU4ZWNhXHU0ZTIxXHUzMDZmXHU2NzAwXHUzMDgyXHU4ZWNhXHU1ZWFiXHUzMDZlXHU1MTY1XHUzMDhhXHU1M2UzXHUzMDZiXHU4ZmQxXHUzMDQ0XHU4ZWNhXHU0ZTIxXHUzMDZlXHUzMDdmXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDRjXHVmZjBjXHUzMDY5XHUzMDYxXHUzMDg5XHUzMDZlXHU4ZWNhXHU1ZWFiXHUzMDRiXHUzMDg5XHU4ZWNhXHU0ZTIxXHUzMDkyXHU1MWZhXHUzMDU5XHUzMDRiXHUzMDZlXHU5ODA2XHU3NTZhXHUzMDZiXHUzMDY0XHUzMDQ0XHUzMDY2XHUzMDZmXHU4MWVhXHU3NTMxXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA1OVx1MzA4Ylx1NTI0ZFx1MzA2Ylx1ZmYwY1x1OGVjYVx1NGUyMVx1MzA5Mlx1NTk3ZFx1MzA0ZFx1MzA2YVx1MzA2MFx1MzA1MVx1OGVjYVx1NWVhYlx1MzA0Ylx1MzA4OVx1NTFmYVx1MzA1N1x1MzA2Nlx1NTIyNVx1MzA2ZVx1NWY4NVx1NmE1Zlx1NzUyOFx1MzBlY1x1MzBmY1x1MzBlYlx1MzA2Ylx1NzlmYlx1MzA1OVx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZVx1NGUwMFx1NWVhNlx1NWY4NVx1NmE1Zlx1NzUyOFx1MzBlY1x1MzBmY1x1MzBlYlx1MzA2Ylx1NzlmYlx1MzA1N1x1MzA1Zlx1OGVjYVx1NGUyMVx1MzA2Zlx1NGVjYVx1NWY4Y1x1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA1OVx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2Ylx1NGY3Zlx1MzA0Nlx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY1x1NGUwMFx1NWVhNlx1NTIxN1x1OGVjYVx1MzA2ZVx1N2RlOFx1NjIxMFx1MzA5Mlx1NTljYlx1MzA4MVx1MzA4Ylx1MzA2OFx1MzA1ZFx1MzA2ZVx1N2RlOFx1NjIxMFx1MzA0Y1x1N2Q0Mlx1MzA4Zlx1MzA4Ylx1MzA3ZVx1MzA2N1x1MzA2ZVx1OTU5M1x1MzA2Zlx1OGVjYVx1NGUyMVx1MzA5Mlx1OGVjYVx1NWVhYlx1MzA0Ylx1MzA4OVx1NWY4NVx1NmE1Zlx1NzUyOFx1MzBlY1x1MzBmY1x1MzBlYlx1MzA2Ylx1NzlmYlx1MzA1OVx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNTlcdTMwOGJcdTMwNjhcdTMwNGRcdWZmMGNcdThlY2FcdTVlYWJcdTUxODVcdTMwNmVcdTUxNjhcdTMwNjZcdTMwNmVcdThlY2FcdTRlMjFcdTMwOTJcdTRmN2ZcdTMwNDRcdTUyMDdcdTMwOGJcdTVmYzVcdTg5ODFcdTMwNmZcdTMwNmFcdTMwNDRcdWZmMGVcdTMwNTlcdTMwNmFcdTMwOGZcdTMwNjFcdWZmMGNcdTUyMTdcdThlY2FcdTMwNmVcdTdkZThcdTYyMTBcdTMwOTJcdTdkNDJcdTMwNDhcdTMwNWZcdTVmOGNcdWZmMGNcdThlY2FcdTVlYWJcdTUxODVcdTMwNmJcdTRmN2ZcdTMwOGZcdTMwOGNcdTMwNmFcdTMwNGJcdTMwNjNcdTMwNWZcdThlY2FcdTRlMjFcdTMwNGNcdTZiOGJcdTMwNjNcdTMwNjZcdTMwNDRcdTMwNjZcdTMwODJcdTY5Y2JcdTMwOGZcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+SU9JIFx1NTZmZFx1MzA2N1x1MzA2Zlx1OTI0NFx1OTA1M1x1MzA2Ylx1NGU1N1x1MzA4Ylx1NGViYVx1MzA0Y1x1MzA2OFx1MzA2Nlx1MzA4Mlx1MzA1Zlx1MzA0Zlx1MzA1NVx1MzA5M1x1MzA0NFx1MzA4Ylx1MzA2OFx1ODAwM1x1MzA0OFx1MzA4OVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA2ZVx1MzA2N1x1ZmYwY1x1MzA2N1x1MzA0ZFx1MzA4Ylx1MzA2MFx1MzA1MVx1OTU3N1x1MzA0NFx1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA1N1x1MzA1Zlx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMzXC90cmFpbi5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDlweDsgd2lkdGg6NTQycHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHU1NmYzOiBcdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNTdcdTMwNjZcdTMwNDRcdTMwOGJcdTkwMTRcdTRlMmRcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTMwNTNcdTMwNmVcdTMwNjhcdTMwNGRcdThlY2FcdTVlYWJcdTMwNmJcdTMwNDJcdTMwOGJcdThlY2FcdTRlMjFcdTMwOTJcdTVmODVcdTZhNWZcdTc1MjhcdTMwZWNcdTMwZmNcdTMwZWJcdTMwNmJcdTc5ZmJcdTMwNTlcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdWZmMGVcdTMwNTNcdTMwNmVcdTU2ZjNcdTMwNmZcdTUxNjVcdTUxZmFcdTUyOWJcdTRmOGIgMSBcdTMwNmJcdTViZmVcdTVmZGNcdTMwNTdcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU4ZWNhXHU1ZWFiXHUzMDZiXHU2ODNjXHU3ZDBkXHUzMDU1XHUzMDhjXHUzMDVmXHU4ZWNhXHU0ZTIxXHUzMDZlXHU2MGM1XHU1ODMxXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjXHU3ZGU4XHU2MjEwXHUzMDY3XHUzMDRkXHUzMDhiXHU1MjE3XHU4ZWNhXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDZlXHU2NzAwXHU1OTI3XHU1MDI0XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHUzMDZlXHU4ZWNhXHU1ZWFiXHUzMDZiXHU2ODNjXHU3ZDBkXHUzMDU1XHUzMDhjXHUzMDVmXHU4ZWNhXHU0ZTIxXHUzMDZlXHU1MjE3XHUzMDZmIDIgXHU3YTJlXHU5ODVlXHUzMDZlXHU2NTg3XHU1YjU3IEksIE8gXHUzMDZlXHUzMDdmXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDY3XHU4ODY4XHUzMDU1XHUzMDhjXHVmZjBjIDIgXHUzMDY0XHUzMDZlXHU4ZWNhXHU1ZWFiXHUzMDZlXHU2MGM1XHU1ODMxXHUzMDZmXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHU5NTc3XHUzMDU1IE0gXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDRhXHUzMDg4XHUzMDczXHU5NTc3XHUzMDU1IE4gXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3IFQgXHUzMDY4XHUzMDU3XHUzMDY2XHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHVmZjBlXHU1NDA0XHU2NTg3XHU1YjU3XHUzMDRjIDEgXHUzMDY0XHUzMDZlXHU4ZWNhXHU0ZTIxXHUzMDkyXHU4ODY4XHUzMDU3XHVmZjBjXHUzMDVkXHUzMDZlXHU2NTg3XHU1YjU3XHUzMDZmXHU4ZWNhXHU0ZTIxXHUzMDZlXHU3YTJlXHU5ODVlXHUzMDY4XHU1NDBjXHUzMDU4XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlIDEgXHU2NTg3XHU1YjU3XHU3NmVlXHUzMDZmXHU2NzAwXHUzMDgyXHU4ZWNhXHU1ZWFiXHUzMDZlXHU1MTY1XHUzMDhhXHU1M2UzXHUzMDZiXHU4ZmQxXHUzMDQ0XHU4ZWNhXHU0ZTIxXHUzMDkyXHU4ODY4XHUzMDU3XHVmZjBjXHU2NzJiXHU1YzNlXHUzMDZlXHU2NTg3XHU1YjU3XHUzMDRjXHU4ZWNhXHU1ZWFiXHUzMDZlXHU2NzAwXHUzMDgyXHU1OTY1XHUzMDZiXHUzMDQyXHUzMDhiXHU4ZWNhXHU0ZTIxXHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2ZiBNLCBOIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2N1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4yIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjU4N1x1NWI1N1x1NTIxNyBTIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4zIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjU4N1x1NWI1N1x1NTIxNyBUIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1NTIzNlx1OTY1MDxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBNICZsZTsgMiAwMDAgXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZlXHU5NTc3XHUzMDU1PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMiAwMDAgXHU2NTg3XHU1YjU3XHU1MjE3IFQgXHUzMDZlXHU5NTc3XHUzMDU1PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxZmFcdTUyOWJcdTMwNmJcdWZmMGNcdTdkZThcdTYyMTBcdTMwNjdcdTMwNGRcdTMwOGJcdTUyMTdcdThlY2FcdTMwNmVcdTk1NzdcdTMwNTVcdTMwNmVcdTY3MDBcdTU5MjdcdTUwMjRcdTMwOTJcdTg4NjhcdTMwNTlcdTY1NzRcdTY1NzBcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGUgXHU1MjE3XHU4ZWNhXHUzMDRjIDEgXHUzMDY0XHUzMDgyXHU3ZGU4XHU2MjEwXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHU1ODM0XHU1NDA4XHUzMDZmXHVmZjBjIDAgXHUzMDkyXHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 > JOI 2013 2번