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

문제

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

예제 입력 2

5 9
IIIII
IIIIIIIII

예제 출력 2

1
W3sicHJvYmxlbV9pZCI6IjU1MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZWNcdWI4MjRcdWI3N2MgSU9JIFx1YzVmNFx1Y2MyOCIsImRlc2NyaXB0aW9uIjoiPHA+SU9JIFx1YWQ2ZFx1YWMwMFx1YjI5NCBcdWNkNWNcdWFkZmMgXHVjMGM4XHViODVjXHVjNmI0IFx1YzVmNFx1Y2MyOCBcdWIxNzhcdWMxMjBcdWM3NzggSU9JXHVjMTIwXHVjNzQ0IFx1YWMxY1x1ZDFiNVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+SU9JIFx1YzVmNFx1Y2MyOFx1YjI5NCBcdWQ1NWMgXHVjZTc4XHVjOWRjXHViOWFjIFx1YjJlOFx1YzcwNCBcdWM1ZjRcdWNjMjggXHVjNWVjXHViN2VjIFx1YjMwMFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViYWE4XHVjMmI1XHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAgXHViMmU4XHVjNzA0IFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWM4ODVcdWI5NThcdWIyOTQgSSBcdWI2MTBcdWIyOTQgT1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ4XHVjODA0XHVjNzQ0IFx1YzcwNFx1ZDU3NCBJT0kgXHVjNWY0XHVjYzI4XHVjNzU4IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4ODVcdWI5NThcdWM1ZWNcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWM2YjRcdWM4MDRcdWMxMWRcdWM3NDAgSVx1Y2U3OFx1YzVkMFx1YjljYyBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWM1OTEgXHViMDVkIFx1Y2U3OFx1Yzc0MCBcdWQ1NmRcdWMwYzEgSVx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgT0lPSVx1YjA5OCBJT09JXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM1ZjRcdWNjMjhcdWIyOTQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZjRcdWNjMjhcdWIyOTQgXHVhYzAxIFx1Y2MyOFx1YjdjOVx1Yzc1OCBcdWM4ODVcdWI5NThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjZTcgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM1ZjRcdWNjMjggSU9JT0lcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDVcdWM3NzRcdWJhNzAgXHVjNWY0XHVjYzI4IElcdWIyOTQgXHVhZTM4XHVjNzc0IDFcdWM3NTggXHVjNWY0XHVjYzI4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIElPSVx1YzEyMFx1Yzc1OCBcdWFjMWNcdWQxYjUgXHVjODA0XHViMGEwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWRcdWMwYWNcdWM4MDFcdWM3NzggXHVjY2FiIFx1YzZiNFx1ZDU4OVx1Yzc0NCBcdWI5ZTFcdWFjOGMgXHViNDFjIFx1Y2MyOFx1YzdhNSBcdWMyYjlcdWQwZGRcdWM3NzRcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjMmI5XHVhYzFkXHVjNzQ0IFx1ZDBkY1x1YzZiOCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1ZDYwNFx1YzdhYyBcdWJjZjRcdWFkMDAgXHVjOTExXHVjNzc4IFx1YjJlOFx1YzcwNCBcdWM1ZjRcdWNjMjhcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1YzVlYyBcdWQ1NWMgXHViMzAwXHVjNzU4IFx1YWUzNCBJT0kgXHVjNWY0XHVjYzI4XHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWIyZThcdWM3MDQgXHVjNWY0XHVjYzI4IEkgXHViNjEwXHViMjk0IE8gXHVjNWVjXHViN2VjIFx1YjMwMFx1YWMwMCBcdWI0NTAgXHVjYzI4XHVhY2UwXHVjOWMwXHVjNWQwIFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWM4ZmNcdWNjMjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjYzI4XHVhY2UwXHVjOWMwIFx1YzkxMSBcdWM1YjRcdWI1MTRcdWMxMWMgXHVjNWY0XHVjYzI4XHViOTdjIFx1YWViY1x1YjBiYyBcdWM5YzBcdWIyOTQgXHVjNzkwXHVjNzIwXHVjOWMwXHViOWNjLCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHViNGU0XHVjNWI0XHVjMTFjIFx1YzYyZVx1YWUzOCBcdWMyMThcdWIyOTQgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWNjMjhcdWFjZTBcdWM3NTggXHVjNzg1XHVhZDZjXHVjNWQwIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWM1ZjRcdWNjMjhcdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHVjYzI4XHViODQwIFx1YWViY1x1YjBiYyBcdWMyMThcdWJjMTZcdWM1ZDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTgsIFx1YzVmNFx1Y2MyOCBcdWQzYjhcdWMxMzFcdWM3NzQgXHVjMmRjXHVjNzkxXHViNDE4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWFjMDEgXHVjYzI4XHVhY2UwXHVjOWMwXHVjNWQwXHVjMTFjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2NcdWM1MjkgXHVjNWY0XHVjYzI4XHViOTdjIFx1YmJmOFx1YjlhYyBcdWM2NzhcdWJkODAgXHVjYzI4XHVhY2UwXHViODVjIFx1YmNmNFx1YjBiNFx1YjQ1OCBcdWMyMThcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHViYzg4IFx1YzY3OFx1YmQ4MCBcdWNjMjhcdWFjZTBcdWI4NWMgXHViY2Y0XHViMGI4IFx1YzVmNFx1Y2MyOFx1Y2U3OFx1Yzc0MCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVkM2I4XHVjMTMxXHVkNTYwIFx1YjU0YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNjEwXHVkNTVjIFx1ZDU1YyBcdWJjODggXHVjNWY0XHVjYzI4IFx1ZDNiOFx1YzEzMVx1Yzc3NCBcdWMyZGNcdWM3OTFcdWI0MWMgXHViMmU0XHVjNzRjXHVjNWQ0IFx1YzY3OFx1YmQ4MCBcdWNjMjhcdWFjZTBcdWI4NWMgXHVjNWY0XHVjYzI4XHViOTdjIFx1YmNmNFx1YjBiYyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIHNyYz1cIlwvdXNlcnVwbG9hZFwvcG9ydGFibGVhbmdlbFwvMjAxNTAzXC9mYTIxNDY4MWFiMDY2N2NlOTg4NmRjNDAwN2QwOWY4MC5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHViMjk0IFx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVjNzUxXHVkNTU4XHViMjk0IFx1YWRmOFx1YjliY1x1Yzc3NFx1YjJlNC4gXHVjNWY0XHVjYzI4IFx1ZDNiOFx1YzEzMVx1Yzc3NCBcdWMyZGNcdWM3OTFcdWI0MThcdWJhNzQgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWM2NzhcdWJkODAgXHVjYzI4XHVhY2UwXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHVjNzNjXHViYTcwLDxcL3A+XHJcblxyXG48cD5cdWM2NzhcdWJkODAgXHVjYzI4XHVhY2UwXHVjNzU4IFx1YzVmNFx1Y2MyOFx1YjI5NCBcdWM1ZjRcdWNjMjggXHVkM2I4XHVjMTMxXHVjNWQwIFx1Yzc3NFx1YzZhOVx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYjlcdWQwZGRcdWM3NzRcdWIyOTQgXHVjODAxXHVjODA4XHVkNzg4IFx1Y2MyOFx1YjdjOSBcdWIzMDBcdWFlMzBcdWMxOGNcdWI4NWMgXHVjNWY0XHVjYzI4XHViOTdjIFx1YmNmNFx1YjBiOCBcdWI0YTQgXHVhZGRjXHVjZTU5XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVjNzc0XHVjNWI0XHViZDk5XHVjNWVjIFx1ZDU1YyBcdWIzMDBcdWM3NTggXHVhZTM0IElPSSBcdWM1ZjRcdWNjMjhcdWI5N2MgXHViOWNjXHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjIFx1YzViY1x1YjljOFx1YjA5OCBcdWFlMzQgXHVjNWY0XHVjYzI4XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWNjMjhcdWFjZTAgU1x1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MWMgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzIxOCBOLCBcdWNjMjhcdWFjZTAgVFx1YzVkMCBcdWM4ZmNcdWNjMjhcdWI0MWMgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMjAwMCwgMSAmbGU7IE0gJmxlOyAyMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjMjhcdWFjZTAgU1x1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MWMgXHVjNWY0XHVjYzI4XHViNGU0XHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzI4XHVhY2UwIFRcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDFjIFx1YzVmNFx1Y2MyOFx1YjRlNFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWNjYWIgXHVhZTAwXHVjNzkwXHVhYzAwIFx1Y2MyOFx1YWNlMFx1Yzc1OCBcdWM3ODVcdWFkNmMgXHVjYWJkXHVjNWQwIFx1YzhmY1x1Y2MyOFx1YjQxYyBcdWM1ZjRcdWNjMjhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZjRcdWNjMjhcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTUyOCIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6IklPSSBcdTUyMTdcdThlY2FcdTMwNjdcdTg4NGNcdTMwNTNcdTMwNDYgKFRha2UgdGhlIFx1MjAxOElPSVx1MjAxOSB0cmFpbikiLCJkZXNjcmlwdGlvbiI6IjxwPklPSSBcdTU2ZmRcdTMwNjdcdTMwNmZcdTMwNTNcdTMwNmVcdTMwNWZcdTMwNzNcdTY1YjBcdTMwNWZcdTMwNmJcdTkyNDRcdTkwNTNcdTMwOTJcdTY1NzdcdThhMmRcdTMwNTdcdTMwNWZcdWZmMGVJT0kgXHU1NmZkXHUzMDZlXHU5MjQ0XHU5MDUzXHUzMDkyXHU4ZDcwXHUzMDhiXHU1MjE3XHU4ZWNhXHUzMDZmXHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU4ZWNhXHU0ZTIxXHUzMDRjXHU5MDIzXHU3ZDUwXHUzMDU1XHUzMDhjXHUzMDVmXHUzMDgyXHUzMDZlXHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjXHU4ZWNhXHU0ZTIxXHUzMDZiXHUzMDZmIEksIE8gXHUzMDZlIDIgXHU3YTJlXHU5ODVlXHUzMDRjXHUzMDQyXHUzMDhiXHVmZjBlXHU4ZWNhXHU0ZTIxXHUzMDZmXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHU3NTcwXHUzMDZhXHUzMDhiXHU3YTJlXHU5ODVlXHUzMDZlXHU4ZWNhXHU0ZTIxXHUzMDY4XHUzMDU3XHUzMDRiXHU5MDIzXHU3ZDUwXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDdlXHUzMDVmXHVmZjBjXHU1MjE3XHU4ZWNhXHUzMDZiXHU5MDRiXHU4ZWUyXHU1ZTJkXHUzMDkyXHU4YTJkXHUzMDUxXHUzMDhiXHU5NWEyXHU0ZmMyXHU0ZTBhXHVmZjBjXHU1MjE3XHU4ZWNhXHUzMDZlXHU0ZTIxXHU3YWVmXHUzMDZlXHU4ZWNhXHU0ZTIxXHUzMDZmXHU3YTJlXHU5ODVlIEkgXHUzMDY3XHUzMDZhXHUzMDUxXHUzMDhjXHUzMDcwXHUzMDZhXHUzMDg5XHUzMDZhXHUzMDQ0XHVmZjBlXHU1MjE3XHU4ZWNhXHUzMDZmXHU4ZWNhXHU0ZTIxXHUzMDZlXHU3YTJlXHU5ODVlXHUzMDkyXHU4ODY4XHUzMDU5XHU2NTg3XHU1YjU3XHUzMDkyXHU5ODA2XHUzMDZiXHUzMDY0XHUzMDZhXHUzMDUyXHUzMDVmXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDY3XHU4ODY4XHUzMDU1XHUzMDhjXHVmZjBjXHU1MjE3XHU4ZWNhXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDZmXHUzMDVkXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDZlXHU5NTc3XHUzMDU1XHUzMDY3XHUzMDQyXHUzMDhiXHUzMDY4XHUzMDU5XHUzMDhiXHVmZjBlXHUzMDVmXHUzMDY4XHUzMDQ4XHUzMDcwXHVmZjBjIElPSU9JIFx1MzA2ZVx1OTgwNlx1MzA2Ylx1OGVjYVx1NGUyMVx1MzA5Mlx1OTAyM1x1N2Q1MFx1MzA1OVx1MzA4Ylx1MzA2OFx1OTU3N1x1MzA1NSA1IFx1MzA2ZVx1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA2N1x1MzA0ZFx1ZmYwY1x1MzA3ZVx1MzA1Zlx1OGVjYVx1NGUyMSBJIFx1MzA2Zlx1NTM1OFx1NzJlY1x1MzA2N1x1OTU3N1x1MzA1NSAxIFx1MzA2ZVx1NTIxN1x1OGVjYVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1OGVjYVx1NGUyMVx1MzA5MiBPSU9JIFx1MzA4NElPT0kgXHUzMDY4XHUzMDQ0XHUzMDYzXHUzMDVmXHU5ODA2XHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDY2XHUzMDgyXHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZmXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzA0NFx1MzA0Zlx1MzA2NFx1MzA0Ylx1MzA2ZVx1OGVjYVx1NGUyMVx1MzA0YyAyIFx1MzA2NFx1MzA2ZVx1OGVjYVx1NWVhYlx1MzA2Ylx1NjgzY1x1N2QwZFx1MzA1NVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1MzA2ZVx1OGVjYVx1NWVhYlx1MzA2ZVx1NGUyZFx1MzA2Ylx1MzA2Zlx1OGVjYVx1NGUyMVx1MzA0Y1x1NGUwMFx1NTIxN1x1MzA2Ylx1NGUyNlx1MzA5M1x1MzA2N1x1MzA0NFx1MzA4Ylx1ZmYwZVx1NTIxN1x1OGVjYVx1MzA5Mlx1N2RlOFx1NjIxMFx1MzA1OVx1MzA4Ylx1MzA2OFx1MzA0ZFx1MzA2Zlx1OGVjYVx1NWVhYlx1MzA0Ylx1MzA4OVx1OGVjYVx1NGUyMVx1MzA5Mlx1NTFmYVx1MzA1N1x1MzA2Nlx1MzA0ZFx1MzA2Nlx1OGVjYVx1NWVhYlx1NTI0ZFx1MzA2N1x1OTAyM1x1N2Q1MFx1MzA1N1x1MzA2Nlx1MzA0NFx1MzA0Zlx1ZmYwZVx1OGVjYVx1NWVhYlx1MzA0Ylx1MzA4OVx1NTFmYVx1MzA1Ylx1MzA4Ylx1OGVjYVx1NGUyMVx1MzA2Zlx1NjcwMFx1MzA4Mlx1OGVjYVx1NWVhYlx1MzA2ZVx1NTE2NVx1MzA4YVx1NTNlM1x1MzA2Ylx1OGZkMVx1MzA0NFx1OGVjYVx1NGUyMVx1MzA2ZVx1MzA3Zlx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA0Y1x1ZmYwY1x1MzA2OVx1MzA2MVx1MzA4OVx1MzA2ZVx1OGVjYVx1NWVhYlx1MzA0Ylx1MzA4OVx1OGVjYVx1NGUyMVx1MzA5Mlx1NTFmYVx1MzA1OVx1MzA0Ylx1MzA2ZVx1OTgwNlx1NzU2YVx1MzA2Ylx1MzA2NFx1MzA0NFx1MzA2Nlx1MzA2Zlx1ODFlYVx1NzUzMVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNTlcdTMwOGJcdTUyNGRcdTMwNmJcdWZmMGNcdThlY2FcdTRlMjFcdTMwOTJcdTU5N2RcdTMwNGRcdTMwNmFcdTMwNjBcdTMwNTFcdThlY2FcdTVlYWJcdTMwNGJcdTMwODlcdTUxZmFcdTMwNTdcdTMwNjZcdTUyMjVcdTMwNmVcdTVmODVcdTZhNWZcdTc1MjhcdTMwZWNcdTMwZmNcdTMwZWJcdTMwNmJcdTc5ZmJcdTMwNTlcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGVcdTRlMDBcdTVlYTZcdTVmODVcdTZhNWZcdTc1MjhcdTMwZWNcdTMwZmNcdTMwZWJcdTMwNmJcdTc5ZmJcdTMwNTdcdTMwNWZcdThlY2FcdTRlMjFcdTMwNmZcdTRlY2FcdTVmOGNcdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNTlcdTMwOGJcdTMwNWZcdTMwODFcdTMwNmJcdTRmN2ZcdTMwNDZcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdWZmMGVcdTMwN2VcdTMwNWZcdWZmMGNcdTRlMDBcdTVlYTZcdTUyMTdcdThlY2FcdTMwNmVcdTdkZThcdTYyMTBcdTMwOTJcdTU5Y2JcdTMwODFcdTMwOGJcdTMwNjhcdTMwNWRcdTMwNmVcdTdkZThcdTYyMTBcdTMwNGNcdTdkNDJcdTMwOGZcdTMwOGJcdTMwN2VcdTMwNjdcdTMwNmVcdTk1OTNcdTMwNmZcdThlY2FcdTRlMjFcdTMwOTJcdThlY2FcdTVlYWJcdTMwNGJcdTMwODlcdTVmODVcdTZhNWZcdTc1MjhcdTMwZWNcdTMwZmNcdTMwZWJcdTMwNmJcdTc5ZmJcdTMwNTlcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU5XHUzMDhiXHUzMDY4XHUzMDRkXHVmZjBjXHU4ZWNhXHU1ZWFiXHU1MTg1XHUzMDZlXHU1MTY4XHUzMDY2XHUzMDZlXHU4ZWNhXHU0ZTIxXHUzMDkyXHU0ZjdmXHUzMDQ0XHU1MjA3XHUzMDhiXHU1ZmM1XHU4OTgxXHUzMDZmXHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDU5XHUzMDZhXHUzMDhmXHUzMDYxXHVmZjBjXHU1MjE3XHU4ZWNhXHUzMDZlXHU3ZGU4XHU2MjEwXHUzMDkyXHU3ZDQyXHUzMDQ4XHUzMDVmXHU1ZjhjXHVmZjBjXHU4ZWNhXHU1ZWFiXHU1MTg1XHUzMDZiXHU0ZjdmXHUzMDhmXHUzMDhjXHUzMDZhXHUzMDRiXHUzMDYzXHUzMDVmXHU4ZWNhXHU0ZTIxXHUzMDRjXHU2YjhiXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDY2XHUzMDgyXHU2OWNiXHUzMDhmXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuXHJcbjxwPklPSSBcdTU2ZmRcdTMwNjdcdTMwNmZcdTkyNDRcdTkwNTNcdTMwNmJcdTRlNTdcdTMwOGJcdTRlYmFcdTMwNGNcdTMwNjhcdTMwNjZcdTMwODJcdTMwNWZcdTMwNGZcdTMwNTVcdTMwOTNcdTMwNDRcdTMwOGJcdTMwNjhcdTgwMDNcdTMwNDhcdTMwODlcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNmVcdTMwNjdcdWZmMGNcdTMwNjdcdTMwNGRcdTMwOGJcdTMwNjBcdTMwNTFcdTk1NzdcdTMwNDRcdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNTdcdTMwNWZcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzM1wvdHJhaW4ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ5cHg7IHdpZHRoOjU0MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlx1NTZmMzogXHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU3XHUzMDY2XHUzMDQ0XHUzMDhiXHU5MDE0XHU0ZTJkXHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjXHUzMDUzXHUzMDZlXHUzMDY4XHUzMDRkXHU4ZWNhXHU1ZWFiXHUzMDZiXHUzMDQyXHUzMDhiXHU4ZWNhXHU0ZTIxXHUzMDkyXHU1Zjg1XHU2YTVmXHU3NTI4XHUzMGVjXHUzMGZjXHUzMGViXHUzMDZiXHU3OWZiXHUzMDU5XHUzMDUzXHUzMDY4XHUzMDZmXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDUzXHUzMDZlXHU1NmYzXHUzMDZmXHU1MTY1XHU1MWZhXHU1MjliXHU0ZjhiIDEgXHUzMDZiXHU1YmZlXHU1ZmRjXHUzMDU3XHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1OGVjYVx1NWVhYlx1MzA2Ylx1NjgzY1x1N2QwZFx1MzA1NVx1MzA4Y1x1MzA1Zlx1OGVjYVx1NGUyMVx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA1Zlx1MzA2OFx1MzA0ZFx1ZmYwY1x1N2RlOFx1NjIxMFx1MzA2N1x1MzA0ZFx1MzA4Ylx1NTIxN1x1OGVjYVx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZVx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1MzA2ZVx1OGVjYVx1NWVhYlx1MzA2Ylx1NjgzY1x1N2QwZFx1MzA1NVx1MzA4Y1x1MzA1Zlx1OGVjYVx1NGUyMVx1MzA2ZVx1NTIxN1x1MzA2ZiAyIFx1N2EyZVx1OTg1ZVx1MzA2ZVx1NjU4N1x1NWI1NyBJLCBPIFx1MzA2ZVx1MzA3Zlx1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2N1x1ODg2OFx1MzA1NVx1MzA4Y1x1ZmYwYyAyIFx1MzA2NFx1MzA2ZVx1OGVjYVx1NWVhYlx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA2Zlx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1OTU3N1x1MzA1NSBNIFx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxNyBTIFx1MzA0YVx1MzA4OFx1MzA3M1x1OTU3N1x1MzA1NSBOIFx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxNyBUIFx1MzA2OFx1MzA1N1x1MzA2Nlx1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1ZmYwZVx1NTQwNFx1NjU4N1x1NWI1N1x1MzA0YyAxIFx1MzA2NFx1MzA2ZVx1OGVjYVx1NGUyMVx1MzA5Mlx1ODg2OFx1MzA1N1x1ZmYwY1x1MzA1ZFx1MzA2ZVx1NjU4N1x1NWI1N1x1MzA2Zlx1OGVjYVx1NGUyMVx1MzA2ZVx1N2EyZVx1OTg1ZVx1MzA2OFx1NTQwY1x1MzA1OFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1NjU4N1x1NWI1N1x1NTIxN1x1MzA2ZSAxIFx1NjU4N1x1NWI1N1x1NzZlZVx1MzA2Zlx1NjcwMFx1MzA4Mlx1OGVjYVx1NWVhYlx1MzA2ZVx1NTE2NVx1MzA4YVx1NTNlM1x1MzA2Ylx1OGZkMVx1MzA0NFx1OGVjYVx1NGUyMVx1MzA5Mlx1ODg2OFx1MzA1N1x1ZmYwY1x1NjcyYlx1NWMzZVx1MzA2ZVx1NjU4N1x1NWI1N1x1MzA0Y1x1OGVjYVx1NWVhYlx1MzA2ZVx1NjcwMFx1MzA4Mlx1NTk2NVx1MzA2Ylx1MzA0Mlx1MzA4Ylx1OGVjYVx1NGUyMVx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MTY1XHU1MjliXHUzMDRiXHUzMDg5XHU0ZWU1XHU0ZTBiXHUzMDZlXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDkyXHU4YWFkXHUzMDdmXHU4ZmJjXHUzMDgxXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmYgTSwgTiBcdTMwNGNcdTdhN2FcdTc2N2RcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjdcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+MiBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9saT5cclxuXHQ8bGk+MyBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTY1ODdcdTViNTdcdTUyMTcgVCBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTFmYVx1NTI5Ylx1MzA2Ylx1ZmYwY1x1N2RlOFx1NjIxMFx1MzA2N1x1MzA0ZFx1MzA4Ylx1NTIxN1x1OGVjYVx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MFx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZSBcdTUyMTdcdThlY2FcdTMwNGMgMSBcdTMwNjRcdTMwODJcdTdkZThcdTYyMTBcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdTU4MzRcdTU0MDhcdTMwNmZcdWZmMGMgMCBcdTMwOTJcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTSAmbGU7IDIgMDAwIFx1NjU4N1x1NWI1N1x1NTIxNyBTIFx1MzA2ZVx1OTU3N1x1MzA1NTxcL2xpPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDIgMDAwIFx1NjU4N1x1NWI1N1x1NTIxNyBUIFx1MzA2ZVx1OTU3N1x1MzA1NTxcL2xpPlxyXG48XC91bD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlMgXHUzMDZiXHUzMDg4XHUzMDYzXHUzMDY2XHU4ODY4XHUzMDU1XHUzMDhjXHUzMDhiXHU4ZWNhXHU1ZWFiXHUzMDkyXHU4ZWNhXHU1ZWFiIFMgXHUzMDY4XHUzMDU3XHVmZjBjVCBcdTMwNmJcdTMwODhcdTMwNjNcdTMwNjZcdTg4NjhcdTMwNTVcdTMwOGNcdTMwOGJcdThlY2FcdTVlYWJcdTMwOTJcdThlY2FcdTVlYWIgVCBcdTMwNjhcdTMwNTdcdTMwODhcdTMwNDZcdWZmMGVcdTMwNTNcdTMwNmVcdTMwNjhcdTMwNGRcdWZmMGNcdTMwNWZcdTMwNjhcdTMwNDggXHUzMDcwXHU4ZWNhXHU1ZWFiIFMgXHUzMDRiXHUzMDg5XHU2NzAwXHU1MjFkXHUzMDZlIDEgXHU4ZWNhXHU0ZTIxXHVmZjBjXHU4ZWNhXHU1ZWFiIFQgXHUzMDRiXHUzMDg5XHU2NzAwXHU1MjFkXHUzMDZlIDIgXHU4ZWNhXHU0ZTIxXHUzMDkyXHU1MWZhXHUzMDU3XHUzMDY2XHU1Zjg1XHU2YTVmXHUzMDU1XHUzMDViXHUzMDVmXHU1ZjhjXHVmZjBjXHU4ZWNhXHU1ZWFiIFNcdWZmMGNcdThlY2FcdTVlYWIgU1x1ZmYwY1x1OGVjYVx1NWVhYiBUXHVmZjBjXHU4ZWNhIFx1NWVhYiBTXHVmZjBjXHU4ZWNhXHU1ZWFiIFNcdWZmMGNcdThlY2FcdTVlYWIgVFx1ZmYwY1x1OGVjYVx1NWVhYiBUIFx1MzA2ZVx1OTgwNlx1NzU2YVx1MzA2Ylx1OGVjYVx1NGUyMVx1MzA5Mlx1NTFmYVx1MzA1Ylx1MzA3MFx1ZmYwY1x1OTU3N1x1MzA1NSA3IFx1MzA2ZVx1NTIxN1x1OGVjYSA8Y29kZT5JT0lPSU9JPFwvY29kZT4gXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDY3XHUzMDRkXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NGVkNlx1MzA2Ylx1MzA4Mlx1ZmYwY1x1OGVjYVx1NWVhYiBTIFx1MzA0Ylx1MzA4OVx1NjcwMFx1NTIxZFx1MzA2ZSAxIFx1OGVjYVx1NGUyMVx1ZmYwY1x1OGVjYVx1NWVhYiBUIFx1MzA0Ylx1MzA4OVx1NjcwMFx1NTIxZFx1MzA2ZSAyIFx1OGVjYVx1NGUyMVx1MzA5Mlx1NTFmYVx1MzA1N1x1MzA2Nlx1NWY4NVx1NmE1Zlx1MzA1NVx1MzA1Ylx1MzA1Zlx1NWY4Y1x1ZmYwY1x1OGVjYVx1NWVhYiBUXHVmZjBjXHU4ZWNhXHU1ZWFiIFRcdWZmMGMgXHU4ZWNhXHU1ZWFiIFNcdWZmMGNcdThlY2FcdTVlYWIgU1x1ZmYwY1x1OGVjYVx1NWVhYiBUXHVmZjBjXHU4ZWNhXHU1ZWFiIFNcdWZmMGNcdThlY2FcdTVlYWIgUyBcdTMwNmVcdTk4MDZcdTc1NmFcdTMwNmJcdThlY2FcdTRlMjFcdTMwOTJcdTUxZmFcdTMwNTlcdTMwNTNcdTMwNjhcdTMwNjdcdTMwODJcdTk1NzdcdTMwNTUgNyBcdTMwNmVcdTUyMTdcdThlY2FcdTMwOTJcdTdkZThcdTYyMTBcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwODggXHUzMDhhXHU5NTc3XHUzMDQ0XHU1MjE3XHU4ZWNhXHUzMDkyXHU3ZGU4XHU2MjEwXHUzMDU5XHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZmXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHUzMDZlXHUzMDY3IDcgXHUzMDkyXHU1MWZhXHU1MjliXHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPjEgXHUzMDY0XHUzMDZlXHU4ZWNhXHU0ZTIxXHUzMDZlXHUzMDdmXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU1MjE3XHU4ZWNhIDxjb2RlPkk8XC9jb2RlPiBcdTMwODJcdTUyMTdcdThlY2FcdTMwNjhcdTMwNTdcdTMwNjZcdTMwNmVcdTY3NjFcdTRlZjZcdTMwOTJcdTZlODBcdTMwNWZcdTMwNTlcdTMwNTNcdTMwNjhcdTMwNmJcdTZjZThcdTYxMGZcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4ifV0=

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2012/2013 2번