시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 127 37 33 32.039%

문제

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+XHJcblx0XHVjNzc0IFx1YjU0YyBcdWM1YmNcdWI5YzhcdWIwOTggXHVhZTM0IFx1YzVmNFx1Y2MyOFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz9cclxuPFwvcD4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjYzI4XHVhY2UwIFNcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDFjIFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWMyMTggTiwgXHVjYzI4XHVhY2UwIFRcdWM1ZDAgXHVjOGZjXHVjYzI4XHViNDFjIFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxIFx1MjI2NCBOIFx1MjI2NCAyMDAwLCAxIFx1MjI2NCBNIFx1MjI2NCAyMDAwKVxyXG48XC9wPlxyXG48cD5cclxuXHRcdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2MyOFx1YWNlMCBTXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWM1ZjRcdWNjMjhcdWI0ZTRcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWMxMzhcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2MyOFx1YWNlMCBUXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWM1ZjRcdWNjMjhcdWI0ZTRcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LlxyXG48XC9wPlxyXG48cD5cclxuXHRcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjY2FiIFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWNjMjhcdWFjZTBcdWM3NTggXHVjNzg1XHVhZDZjIFx1Y2FiZFx1YzVkMCBcdWM4ZmNcdWNjMjhcdWI0MWMgXHVjNWY0XHVjYzI4XHVjNzc0XHViMmU0LlxyXG48XC9wPiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWM1ZjRcdWNjMjhcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC5cclxuPFwvcD5cclxuPHA+XHJcblx0XHVjNWY0XHVjYzI4XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LlxyXG48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1MjgiLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJJT0kgXHU1MjE3XHU4ZWNhXHUzMDY3XHU4ODRjXHUzMDUzXHUzMDQ2IiwiZGVzY3JpcHRpb24iOiI8cD5JT0kgXHU1NmZkXHUzMDY3XHUzMDZmXHUzMDUzXHUzMDZlXHUzMDVmXHUzMDczXHU2NWIwXHUzMDVmXHUzMDZiXHU5MjQ0XHU5MDUzXHUzMDkyXHU2NTc3XHU4YTJkXHUzMDU3XHUzMDVmXHVmZjBlSU9JIFx1NTZmZFx1MzA2ZVx1OTI0NFx1OTA1M1x1MzA5Mlx1OGQ3MFx1MzA4Ylx1NTIxN1x1OGVjYVx1MzA2Zlx1MzA0NFx1MzA0Zlx1MzA2NFx1MzA0Ylx1MzA2ZVx1OGVjYVx1NGUyMVx1MzA0Y1x1OTAyM1x1N2Q1MFx1MzA1NVx1MzA4Y1x1MzA1Zlx1MzA4Mlx1MzA2ZVx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY1x1OGVjYVx1NGUyMVx1MzA2Ylx1MzA2ZiBJLCBPIFx1MzA2ZSAyIFx1N2EyZVx1OTg1ZVx1MzA0Y1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1OGVjYVx1NGUyMVx1MzA2Zlx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1NzU3MFx1MzA2YVx1MzA4Ylx1N2EyZVx1OTg1ZVx1MzA2ZVx1OGVjYVx1NGUyMVx1MzA2OFx1MzA1N1x1MzA0Ylx1OTAyM1x1N2Q1MFx1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY1x1NTIxN1x1OGVjYVx1MzA2Ylx1OTA0Ylx1OGVlMlx1NWUyZFx1MzA5Mlx1OGEyZFx1MzA1MVx1MzA4Ylx1OTVhMlx1NGZjMlx1NGUwYVx1ZmYwY1x1NTIxN1x1OGVjYVx1MzA2ZVx1NGUyMVx1N2FlZlx1MzA2ZVx1OGVjYVx1NGUyMVx1MzA2Zlx1N2EyZVx1OTg1ZSBJIFx1MzA2N1x1MzA2YVx1MzA1MVx1MzA4Y1x1MzA3MFx1MzA2YVx1MzA4OVx1MzA2YVx1MzA0NFx1ZmYwZVx1NTIxN1x1OGVjYVx1MzA2Zlx1OGVjYVx1NGUyMVx1MzA2ZVx1N2EyZVx1OTg1ZVx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU4N1x1NWI1N1x1MzA5Mlx1OTgwNlx1MzA2Ylx1MzA2NFx1MzA2YVx1MzA1Mlx1MzA1Zlx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2N1x1ODg2OFx1MzA1NVx1MzA4Y1x1ZmYwY1x1NTIxN1x1OGVjYVx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2Zlx1MzA1ZFx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA2OFx1MzA1OVx1MzA4Ylx1ZmYwZVx1MzA1Zlx1MzA2OFx1MzA0OFx1MzA3MFx1ZmYwYyBJT0lPSSBcdTMwNmVcdTk4MDZcdTMwNmJcdThlY2FcdTRlMjFcdTMwOTJcdTkwMjNcdTdkNTBcdTMwNTlcdTMwOGJcdTMwNjhcdTk1NzdcdTMwNTUgNSBcdTMwNmVcdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNjdcdTMwNGRcdWZmMGNcdTMwN2VcdTMwNWZcdThlY2FcdTRlMjEgSSBcdTMwNmZcdTUzNThcdTcyZWNcdTMwNjdcdTk1NzdcdTMwNTUgMSBcdTMwNmVcdTUyMTdcdThlY2FcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdThlY2FcdTRlMjFcdTMwOTIgT0lPSSBcdTMwODRJT09JIFx1MzA2OFx1MzA0NFx1MzA2M1x1MzA1Zlx1OTgwNlx1MzA2Ylx1NGUyNlx1MzA3OVx1MzA2Nlx1MzA4Mlx1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA1OVx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTMwNDRcdTMwNGZcdTMwNjRcdTMwNGJcdTMwNmVcdThlY2FcdTRlMjFcdTMwNGMgMiBcdTMwNjRcdTMwNmVcdThlY2FcdTVlYWJcdTMwNmJcdTY4M2NcdTdkMGRcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdThlY2FcdTVlYWJcdTMwNmVcdTRlMmRcdTMwNmJcdTMwNmZcdThlY2FcdTRlMjFcdTMwNGNcdTRlMDBcdTUyMTdcdTMwNmJcdTRlMjZcdTMwOTNcdTMwNjdcdTMwNDRcdTMwOGJcdWZmMGVcdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNTlcdTMwOGJcdTMwNjhcdTMwNGRcdTMwNmZcdThlY2FcdTVlYWJcdTMwNGJcdTMwODlcdThlY2FcdTRlMjFcdTMwOTJcdTUxZmFcdTMwNTdcdTMwNjZcdTMwNGRcdTMwNjZcdThlY2FcdTVlYWJcdTUyNGRcdTMwNjdcdTkwMjNcdTdkNTBcdTMwNTdcdTMwNjZcdTMwNDRcdTMwNGZcdWZmMGVcdThlY2FcdTVlYWJcdTMwNGJcdTMwODlcdTUxZmFcdTMwNWJcdTMwOGJcdThlY2FcdTRlMjFcdTMwNmZcdTY3MDBcdTMwODJcdThlY2FcdTVlYWJcdTMwNmVcdTUxNjVcdTMwOGFcdTUzZTNcdTMwNmJcdThmZDFcdTMwNDRcdThlY2FcdTRlMjFcdTMwNmVcdTMwN2ZcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNGNcdWZmMGNcdTMwNjlcdTMwNjFcdTMwODlcdTMwNmVcdThlY2FcdTVlYWJcdTMwNGJcdTMwODlcdThlY2FcdTRlMjFcdTMwOTJcdTUxZmFcdTMwNTlcdTMwNGJcdTMwNmVcdTk4MDZcdTc1NmFcdTMwNmJcdTMwNjRcdTMwNDRcdTMwNjZcdTMwNmZcdTgxZWFcdTc1MzFcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU5XHUzMDhiXHU1MjRkXHUzMDZiXHVmZjBjXHU4ZWNhXHU0ZTIxXHUzMDkyXHU1OTdkXHUzMDRkXHUzMDZhXHUzMDYwXHUzMDUxXHU4ZWNhXHU1ZWFiXHUzMDRiXHUzMDg5XHU1MWZhXHUzMDU3XHUzMDY2XHU1MjI1XHUzMDZlXHU1Zjg1XHU2YTVmXHU3NTI4XHUzMGVjXHUzMGZjXHUzMGViXHUzMDZiXHU3OWZiXHUzMDU5XHUzMDUzXHUzMDY4XHUzMDRjXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlXHU0ZTAwXHU1ZWE2XHU1Zjg1XHU2YTVmXHU3NTI4XHUzMGVjXHUzMGZjXHUzMGViXHUzMDZiXHU3OWZiXHUzMDU3XHUzMDVmXHU4ZWNhXHU0ZTIxXHUzMDZmXHU0ZWNhXHU1ZjhjXHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU5XHUzMDhiXHUzMDVmXHUzMDgxXHUzMDZiXHU0ZjdmXHUzMDQ2XHUzMDUzXHUzMDY4XHUzMDZmXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDdlXHUzMDVmXHVmZjBjXHU0ZTAwXHU1ZWE2XHU1MjE3XHU4ZWNhXHUzMDZlXHU3ZGU4XHU2MjEwXHUzMDkyXHU1OWNiXHUzMDgxXHUzMDhiXHUzMDY4XHUzMDVkXHUzMDZlXHU3ZGU4XHU2MjEwXHUzMDRjXHU3ZDQyXHUzMDhmXHUzMDhiXHUzMDdlXHUzMDY3XHUzMDZlXHU5NTkzXHUzMDZmXHU4ZWNhXHU0ZTIxXHUzMDkyXHU4ZWNhXHU1ZWFiXHUzMDRiXHUzMDg5XHU1Zjg1XHU2YTVmXHU3NTI4XHUzMGVjXHUzMGZjXHUzMGViXHUzMDZiXHU3OWZiXHUzMDU5XHUzMDUzXHUzMDY4XHUzMDZmXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA1OVx1MzA4Ylx1MzA2OFx1MzA0ZFx1ZmYwY1x1OGVjYVx1NWVhYlx1NTE4NVx1MzA2ZVx1NTE2OFx1MzA2Nlx1MzA2ZVx1OGVjYVx1NGUyMVx1MzA5Mlx1NGY3Zlx1MzA0NFx1NTIwN1x1MzA4Ylx1NWZjNVx1ODk4MVx1MzA2Zlx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA1OVx1MzA2YVx1MzA4Zlx1MzA2MVx1ZmYwY1x1NTIxN1x1OGVjYVx1MzA2ZVx1N2RlOFx1NjIxMFx1MzA5Mlx1N2Q0Mlx1MzA0OFx1MzA1Zlx1NWY4Y1x1ZmYwY1x1OGVjYVx1NWVhYlx1NTE4NVx1MzA2Ylx1NGY3Zlx1MzA4Zlx1MzA4Y1x1MzA2YVx1MzA0Ylx1MzA2M1x1MzA1Zlx1OGVjYVx1NGUyMVx1MzA0Y1x1NmI4Ylx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA2Nlx1MzA4Mlx1NjljYlx1MzA4Zlx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD5JT0kgXHU1NmZkXHUzMDY3XHUzMDZmXHU5MjQ0XHU5MDUzXHUzMDZiXHU0ZTU3XHUzMDhiXHU0ZWJhXHUzMDRjXHUzMDY4XHUzMDY2XHUzMDgyXHUzMDVmXHUzMDRmXHUzMDU1XHUzMDkzXHUzMDQ0XHUzMDhiXHUzMDY4XHU4MDAzXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDZlXHUzMDY3XHVmZjBjXHUzMDY3XHUzMDRkXHUzMDhiXHUzMDYwXHUzMDUxXHU5NTc3XHUzMDQ0XHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU3XHUzMDVmXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczNcL3RyYWluLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0OXB4OyB3aWR0aDo1NDJweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdTU2ZjM6IFx1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA1N1x1MzA2Nlx1MzA0NFx1MzA4Ylx1OTAxNFx1NGUyZFx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY1x1MzA1M1x1MzA2ZVx1MzA2OFx1MzA0ZFx1OGVjYVx1NWVhYlx1MzA2Ylx1MzA0Mlx1MzA4Ylx1OGVjYVx1NGUyMVx1MzA5Mlx1NWY4NVx1NmE1Zlx1NzUyOFx1MzBlY1x1MzBmY1x1MzBlYlx1MzA2Ylx1NzlmYlx1MzA1OVx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA1M1x1MzA2ZVx1NTZmM1x1MzA2Zlx1NTE2NVx1NTFmYVx1NTI5Ylx1NGY4YiAxIFx1MzA2Ylx1NWJmZVx1NWZkY1x1MzA1N1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdThlY2FcdTVlYWJcdTMwNmJcdTY4M2NcdTdkMGRcdTMwNTVcdTMwOGNcdTMwNWZcdThlY2FcdTRlMjFcdTMwNmVcdTYwYzVcdTU4MzFcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNcdTdkZThcdTYyMTBcdTMwNjdcdTMwNGRcdTMwOGJcdTUyMTdcdThlY2FcdTMwNmVcdTk1NzdcdTMwNTVcdTMwNmVcdTY3MDBcdTU5MjdcdTUwMjRcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGVcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdThlY2FcdTVlYWJcdTMwNmJcdTY4M2NcdTdkMGRcdTMwNTVcdTMwOGNcdTMwNWZcdThlY2FcdTRlMjFcdTMwNmVcdTUyMTdcdTMwNmYgMiBcdTdhMmVcdTk4NWVcdTMwNmVcdTY1ODdcdTViNTcgSSwgTyBcdTMwNmVcdTMwN2ZcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTdcdTMwNjdcdTg4NjhcdTMwNTVcdTMwOGNcdWZmMGMgMiBcdTMwNjRcdTMwNmVcdThlY2FcdTVlYWJcdTMwNmVcdTYwYzVcdTU4MzFcdTMwNmZcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTk1NzdcdTMwNTUgTSBcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNGFcdTMwODhcdTMwNzNcdTk1NzdcdTMwNTUgTiBcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTcgVCBcdTMwNjhcdTMwNTdcdTMwNjZcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdWZmMGVcdTU0MDRcdTY1ODdcdTViNTdcdTMwNGMgMSBcdTMwNjRcdTMwNmVcdThlY2FcdTRlMjFcdTMwOTJcdTg4NjhcdTMwNTdcdWZmMGNcdTMwNWRcdTMwNmVcdTY1ODdcdTViNTdcdTMwNmZcdThlY2FcdTRlMjFcdTMwNmVcdTdhMmVcdTk4NWVcdTMwNjhcdTU0MGNcdTMwNThcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTY1ODdcdTViNTdcdTUyMTdcdTMwNmUgMSBcdTY1ODdcdTViNTdcdTc2ZWVcdTMwNmZcdTY3MDBcdTMwODJcdThlY2FcdTVlYWJcdTMwNmVcdTUxNjVcdTMwOGFcdTUzZTNcdTMwNmJcdThmZDFcdTMwNDRcdThlY2FcdTRlMjFcdTMwOTJcdTg4NjhcdTMwNTdcdWZmMGNcdTY3MmJcdTVjM2VcdTMwNmVcdTY1ODdcdTViNTdcdTMwNGNcdThlY2FcdTVlYWJcdTMwNmVcdTY3MDBcdTMwODJcdTU5NjVcdTMwNmJcdTMwNDJcdTMwOGJcdThlY2FcdTRlMjFcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTE2NVx1NTI5Ylx1MzA0Ylx1MzA4OVx1NGVlNVx1NGUwYlx1MzA2ZVx1MzBjN1x1MzBmY1x1MzBiZlx1MzA5Mlx1OGFhZFx1MzA3Zlx1OGZiY1x1MzA4MVx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmIE0sIE4gXHUzMDRjXHU3YTdhXHU3NjdkXHU1MzNhXHU1MjA3XHUzMDhhXHUzMDY3XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPjIgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPjMgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTg3XHU1YjU3XHU1MjE3IFQgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHU1MjM2XHU5NjUwPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyAyIDAwMCBcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNmVcdTk1NzdcdTMwNTU8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAyIDAwMCBcdTY1ODdcdTViNTdcdTUyMTcgVCBcdTMwNmVcdTk1NzdcdTMwNTU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY1x1N2RlOFx1NjIxMFx1MzA2N1x1MzA0ZFx1MzA4Ylx1NTIxN1x1OGVjYVx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MFx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZSBcdTUyMTdcdThlY2FcdTMwNGMgMSBcdTMwNjRcdTMwODJcdTdkZThcdTYyMTBcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdTU4MzRcdTU0MDhcdTMwNmZcdWZmMGMgMCBcdTMwOTJcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM3N2NcdWJjZjhcdWM1YjQifV0=

출처

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