시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 32 30 50.847%

문제

민혁 유치원에서는 아이들의 창의력과 인내력, 근력과 지구력, 잉여력과 탄성력, 판단력과 노력, 기력과 활동력, 활력과 달력, 내구력과 변형력, 응집력과 무력, 지력과 매력, 미력과 담력, 능력과 실력, 압력과 협력, 체력과 경력, 폭력과 세력, 양력과 음력, 입력과 출력, 권력과 주력, 병력과 전력, 마찰력과 동력, 탄성력과 효력, 내력과 국력, 동력과 중력, 화력과 수력, 원자력과 영향력, 이력과 경쟁력, 경제력과 설득력, 공권력과 원동력, 정치력과 집중력, 추진력과 연기력, 잠재력과 정신력, 부력과 재력, 마력과 유력, 조력과 여력, 초능력과 예지력, 표현력과 기억력, 무기력과 창조력, 순발력과 저항력, 호소력과 관찰력, 구속력과 풍력, 청력과 시력, 학력과 필력, 완력과 사력, 수사력과 자생력, 고학력과 번식력, 자금력과 포용력, 정력과 편력, 속력과 피력, 지도력과 통제력, 기동력과 사고력, 무중력과 결정력, 이해력과 친화력, 결단력과 태양력, 공격력과 방어력, 돌파력과 장악력, 전속력과 흡인력, 괴력과 극력, 독력과 경기력, 기획력과 득점력, 적응력과 파괴력, 행정력과 구매력, 도약력과 반발력, 진력과 금력, 강력과 약력, 정치권력과 분석력, 세정력과 자제력, 반작용력과 만유인력, 근지구력과 진심전력, 불가항력과 청천벽력, 폭발력과 형성력, 견제력과 장력, 각력과 감항능력, 겸인지력과 결심육력, 고광지력과 구사력, 단결력과 생활력, 수비력과 운동력, 교정시력과 공력, 어휘력과 군책군력, 구태양력과 조직력, 가창력과 문장력, 발표력과 교력, 궁력과 동심합력, 방위력과 소비력, 연출력과 자본력, 주도력과 그레고리력, 율리우스력과 마호메트력, 무능력과 작용력, 주동력과 가로복원력, 강제통영력과 게이지압력, 경제잠재력과 분투노력, 공소의효력과 불유여력, 직감력과 직관력, 추리력과 충격력, 횡압력과 감별력, 결합력과 기술력, 미적판단력과 발전소출력, 사회적압력과 신통력, 동원력과 가호력, 다력과 대력, 감각력과 감득력, 자기세력과 일심협력, 이집트력과 정지마찰력, 잠재구매력과 최대마찰력, 감상력과 개괄력, 개발력과 개념력, 도력과 구상력, 관통력과 물력, 기조력과 기전력, 담세력과 독서력, 독창력과 법력을 기르기 위해 재미있는 게임을 만들었다.

이 게임을 하려면 한 변의 길이가 N인 정사각형 보드가 필요하다. 이 보드는 변의 길이가 1인 정사각형 N*N개로 나누어져 있다. 또, 변의 길이가 1인 정육면체 블록도 여러 개 있다. 아이들은 이 블록을 보드 위의 한 정사각형 위에 올려놓거나, 다른 블록 위에 올려 놓는다. 항상 블록은 정사각형 하나를 가득 채우게 놓아야 한다.

아이들은 이 놀이를 하고 난 다음에 반드시 뒷정리를 하고 집에 가야 한다. 만약, 뒷정리를 하지 않을 경우에는 민혁 선생님과 력으로 끝나는 단어 외우기를 해야 한다.

선생님은 아이들에게 직사각형을 가르쳐 주기 위해서, 블록을 직사각형 모양으로 배열하라고 했다. 이때, 한 블록 위에 다른 블록이 있으면 안된다.

지금 블록의 상태가 주어졌을 때, 이 블록이 놓인 모습이 직사각형이 되게 하기 위해서 블록을 최소 몇 개 움직여야 하는지 구하는 프로그램을 작성하시오. 한 칸의 가장 위에 있는 블록을 다른 칸의 가장 위에 올려놓는 이동만 할 수 있다.

입력

첫째 줄에 보드판의 한 변의 길이 N과 그 위의 블록의 개수 M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ N2)

다음 M개 줄에는 블록이 있는 위치(좌표) R과 C가 주어진다. (1 ≤ R, C ≤ N)

출력

첫째 줄에 블록을 최소 몇 개 이동시키면 직사각형을 만들 수 있는지 출력한다. 항상 직사각형을 만들 수 있는 경우만 입력으로 주어진다.

예제 입력 1

5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3

예제 출력 1

3

힌트

(2, 3)을 (3, 3)으로, (4, 2)를 (2, 5)로, (4, 4)를 (3, 5)로 이동시키면 직사각형이 된다.

W3sicHJvYmxlbV9pZCI6IjI5MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI4NWQgXHVjODE1XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWJiZmNcdWQ2MDEgXHVjNzIwXHVjZTU4XHVjNmQwXHVjNWQwXHVjMTFjXHViMjk0IFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWNjM2RcdWM3NThcdWI4MjVcdWFjZmMgXHVjNzc4XHViMGI0XHViODI1LCBcdWFkZmNcdWI4MjVcdWFjZmMgXHVjOWMwXHVhZDZjXHViODI1LCBcdWM3ODlcdWM1ZWNcdWI4MjVcdWFjZmMgXHVkMGM0XHVjMTMxXHViODI1LCBcdWQzMTBcdWIyZThcdWI4MjVcdWFjZmMgXHViMTc4XHViODI1LCBcdWFlMzBcdWI4MjVcdWFjZmMgXHVkNjVjXHViM2Q5XHViODI1LCBcdWQ2NWNcdWI4MjVcdWFjZmMgXHViMmVjXHViODI1LCBcdWIwYjRcdWFkNmNcdWI4MjVcdWFjZmMgXHViY2MwXHVkNjE1XHViODI1LCBcdWM3NTFcdWM5ZDFcdWI4MjVcdWFjZmMgXHViYjM0XHViODI1LCBcdWM5YzBcdWI4MjVcdWFjZmMgXHViOWU0XHViODI1LCBcdWJiZjhcdWI4MjVcdWFjZmMgXHViMmY0XHViODI1LCBcdWIyYTVcdWI4MjVcdWFjZmMgXHVjMmU0XHViODI1LCBcdWM1NTVcdWI4MjVcdWFjZmMgXHVkNjExXHViODI1LCBcdWNjYjRcdWI4MjVcdWFjZmMgXHVhY2JkXHViODI1LCBcdWQzZWRcdWI4MjVcdWFjZmMgXHVjMTM4XHViODI1LCBcdWM1OTFcdWI4MjVcdWFjZmMgXHVjNzRjXHViODI1LCBcdWM3ODVcdWI4MjVcdWFjZmMgXHVjZDljXHViODI1LCBcdWFkOGNcdWI4MjVcdWFjZmMgXHVjOGZjXHViODI1LCBcdWJjZDFcdWI4MjVcdWFjZmMgXHVjODA0XHViODI1LCBcdWI5YzhcdWNjMzBcdWI4MjVcdWFjZmMgXHViM2Q5XHViODI1LCBcdWQwYzRcdWMxMzFcdWI4MjVcdWFjZmMgXHVkNmE4XHViODI1LCBcdWIwYjRcdWI4MjVcdWFjZmMgXHVhZDZkXHViODI1LCBcdWIzZDlcdWI4MjVcdWFjZmMgXHVjOTExXHViODI1LCBcdWQ2NTRcdWI4MjVcdWFjZmMgXHVjMjE4XHViODI1LCBcdWM2ZDBcdWM3OTBcdWI4MjVcdWFjZmMgXHVjNjAxXHVkNWE1XHViODI1LCBcdWM3NzRcdWI4MjVcdWFjZmMgXHVhY2JkXHVjN2MxXHViODI1LCBcdWFjYmRcdWM4MWNcdWI4MjVcdWFjZmMgXHVjMTI0XHViNGRkXHViODI1LCBcdWFjZjVcdWFkOGNcdWI4MjVcdWFjZmMgXHVjNmQwXHViM2Q5XHViODI1LCBcdWM4MTVcdWNlNThcdWI4MjVcdWFjZmMgXHVjOWQxXHVjOTExXHViODI1LCBcdWNkOTRcdWM5YzRcdWI4MjVcdWFjZmMgXHVjNWYwXHVhZTMwXHViODI1LCBcdWM3YTBcdWM3YWNcdWI4MjVcdWFjZmMgXHVjODE1XHVjMmUwXHViODI1LCBcdWJkODBcdWI4MjVcdWFjZmMgXHVjN2FjXHViODI1LCBcdWI5YzhcdWI4MjVcdWFjZmMgXHVjNzIwXHViODI1LCBcdWM4NzBcdWI4MjVcdWFjZmMgXHVjNWVjXHViODI1LCBcdWNkMDhcdWIyYTVcdWI4MjVcdWFjZmMgXHVjNjA4XHVjOWMwXHViODI1LCBcdWQ0NWNcdWQ2MDRcdWI4MjVcdWFjZmMgXHVhZTMwXHVjNWI1XHViODI1LCBcdWJiMzRcdWFlMzBcdWI4MjVcdWFjZmMgXHVjYzNkXHVjODcwXHViODI1LCBcdWMyMWNcdWJjMWNcdWI4MjVcdWFjZmMgXHVjODAwXHVkNTZkXHViODI1LCBcdWQ2MzhcdWMxOGNcdWI4MjVcdWFjZmMgXHVhZDAwXHVjYzMwXHViODI1LCBcdWFkNmNcdWMxOGRcdWI4MjVcdWFjZmMgXHVkNDhkXHViODI1LCBcdWNjYWRcdWI4MjVcdWFjZmMgXHVjMmRjXHViODI1LCBcdWQ1NTlcdWI4MjVcdWFjZmMgXHVkNTQ0XHViODI1LCBcdWM2NDRcdWI4MjVcdWFjZmMgXHVjMGFjXHViODI1LCBcdWMyMThcdWMwYWNcdWI4MjVcdWFjZmMgXHVjNzkwXHVjMGRkXHViODI1LCBcdWFjZTBcdWQ1NTlcdWI4MjVcdWFjZmMgXHViYzg4XHVjMmRkXHViODI1LCBcdWM3OTBcdWFlMDhcdWI4MjVcdWFjZmMgXHVkM2VjXHVjNmE5XHViODI1LCBcdWM4MTVcdWI4MjVcdWFjZmMgXHVkM2I4XHViODI1LCBcdWMxOGRcdWI4MjVcdWFjZmMgXHVkNTNjXHViODI1LCBcdWM5YzBcdWIzYzRcdWI4MjVcdWFjZmMgXHVkMWI1XHVjODFjXHViODI1LCBcdWFlMzBcdWIzZDlcdWI4MjVcdWFjZmMgXHVjMGFjXHVhY2UwXHViODI1LCBcdWJiMzRcdWM5MTFcdWI4MjVcdWFjZmMgXHVhY2IwXHVjODE1XHViODI1LCBcdWM3NzRcdWQ1NzRcdWI4MjVcdWFjZmMgXHVjZTVjXHVkNjU0XHViODI1LCBcdWFjYjBcdWIyZThcdWI4MjVcdWFjZmMgXHVkMGRjXHVjNTkxXHViODI1LCBcdWFjZjVcdWFjYTlcdWI4MjVcdWFjZmMgXHViYzI5XHVjNWI0XHViODI1LCBcdWIzY2NcdWQzMGNcdWI4MjVcdWFjZmMgXHVjN2E1XHVjNTQ1XHViODI1LCBcdWM4MDRcdWMxOGRcdWI4MjVcdWFjZmMgXHVkNzYxXHVjNzc4XHViODI1LCBcdWFkMzRcdWI4MjVcdWFjZmMgXHVhZGY5XHViODI1LCBcdWIzYzVcdWI4MjVcdWFjZmMgXHVhY2JkXHVhZTMwXHViODI1LCBcdWFlMzBcdWQ2OGRcdWI4MjVcdWFjZmMgXHViNGRkXHVjODEwXHViODI1LCBcdWM4MDFcdWM3NTFcdWI4MjVcdWFjZmMgXHVkMzBjXHVhZDM0XHViODI1LCBcdWQ1ODlcdWM4MTVcdWI4MjVcdWFjZmMgXHVhZDZjXHViOWU0XHViODI1LCBcdWIzYzRcdWM1N2RcdWI4MjVcdWFjZmMgXHViYzE4XHViYzFjXHViODI1LCBcdWM5YzRcdWI4MjVcdWFjZmMgXHVhZTA4XHViODI1LCBcdWFjMTVcdWI4MjVcdWFjZmMgXHVjNTdkXHViODI1LCBcdWM4MTVcdWNlNThcdWFkOGNcdWI4MjVcdWFjZmMgXHViZDg0XHVjMTFkXHViODI1LCBcdWMxMzhcdWM4MTVcdWI4MjVcdWFjZmMgXHVjNzkwXHVjODFjXHViODI1LCBcdWJjMThcdWM3OTFcdWM2YTlcdWI4MjVcdWFjZmMgXHViOWNjXHVjNzIwXHVjNzc4XHViODI1LCBcdWFkZmNcdWM5YzBcdWFkNmNcdWI4MjVcdWFjZmMgXHVjOWM0XHVjMmVjXHVjODA0XHViODI1LCBcdWJkODhcdWFjMDBcdWQ1NmRcdWI4MjVcdWFjZmMgXHVjY2FkXHVjYzljXHViY2JkXHViODI1LCBcdWQzZWRcdWJjMWNcdWI4MjVcdWFjZmMgXHVkNjE1XHVjMTMxXHViODI1LCBcdWFjYWNcdWM4MWNcdWI4MjVcdWFjZmMgXHVjN2E1XHViODI1LCBcdWFjMDFcdWI4MjVcdWFjZmMgXHVhYzEwXHVkNTZkXHViMmE1XHViODI1LCBcdWFjYjhcdWM3NzhcdWM5YzBcdWI4MjVcdWFjZmMgXHVhY2IwXHVjMmVjXHVjNzIxXHViODI1LCBcdWFjZTBcdWFkMTFcdWM5YzBcdWI4MjVcdWFjZmMgXHVhZDZjXHVjMGFjXHViODI1LCBcdWIyZThcdWFjYjBcdWI4MjVcdWFjZmMgXHVjMGRkXHVkNjVjXHViODI1LCBcdWMyMThcdWJlNDRcdWI4MjVcdWFjZmMgXHVjNmI0XHViM2Q5XHViODI1LCBcdWFkNTBcdWM4MTVcdWMyZGNcdWI4MjVcdWFjZmMgXHVhY2Y1XHViODI1LCBcdWM1YjRcdWQ3MThcdWI4MjVcdWFjZmMgXHVhZDcwXHVjYzQ1XHVhZDcwXHViODI1LCBcdWFkNmNcdWQwZGNcdWM1OTFcdWI4MjVcdWFjZmMgXHVjODcwXHVjOWMxXHViODI1LCBcdWFjMDBcdWNjM2RcdWI4MjVcdWFjZmMgXHViYjM4XHVjN2E1XHViODI1LCBcdWJjMWNcdWQ0NWNcdWI4MjVcdWFjZmMgXHVhZDUwXHViODI1LCBcdWFkODFcdWI4MjVcdWFjZmMgXHViM2Q5XHVjMmVjXHVkNTY5XHViODI1LCBcdWJjMjlcdWM3MDRcdWI4MjVcdWFjZmMgXHVjMThjXHViZTQ0XHViODI1LCBcdWM1ZjBcdWNkOWNcdWI4MjVcdWFjZmMgXHVjNzkwXHViY2Y4XHViODI1LCBcdWM4ZmNcdWIzYzRcdWI4MjVcdWFjZmMgXHVhZGY4XHViODA4XHVhY2UwXHViOWFjXHViODI1LCBcdWM3MjhcdWI5YWNcdWM2YjBcdWMyYTRcdWI4MjVcdWFjZmMgXHViOWM4XHVkNjM4XHViYTU0XHVkMmI4XHViODI1LCBcdWJiMzRcdWIyYTVcdWI4MjVcdWFjZmMgXHVjNzkxXHVjNmE5XHViODI1LCBcdWM4ZmNcdWIzZDlcdWI4MjVcdWFjZmMgXHVhYzAwXHViODVjXHViY2Y1XHVjNmQwXHViODI1LCBcdWFjMTVcdWM4MWNcdWQxYjVcdWM2MDFcdWI4MjVcdWFjZmMgXHVhYzhjXHVjNzc0XHVjOWMwXHVjNTU1XHViODI1LCBcdWFjYmRcdWM4MWNcdWM3YTBcdWM3YWNcdWI4MjVcdWFjZmMgXHViZDg0XHVkMjJjXHViMTc4XHViODI1LCBcdWFjZjVcdWMxOGNcdWM3NThcdWQ2YThcdWI4MjVcdWFjZmMgXHViZDg4XHVjNzIwXHVjNWVjXHViODI1LCBcdWM5YzFcdWFjMTBcdWI4MjVcdWFjZmMgXHVjOWMxXHVhZDAwXHViODI1LCBcdWNkOTRcdWI5YWNcdWI4MjVcdWFjZmMgXHVjZGE5XHVhY2E5XHViODI1LCBcdWQ2YTFcdWM1NTVcdWI4MjVcdWFjZmMgXHVhYzEwXHViY2M0XHViODI1LCBcdWFjYjBcdWQ1NjlcdWI4MjVcdWFjZmMgXHVhZTMwXHVjMjIwXHViODI1LCBcdWJiZjhcdWM4MDFcdWQzMTBcdWIyZThcdWI4MjVcdWFjZmMgXHViYzFjXHVjODA0XHVjMThjXHVjZDljXHViODI1LCBcdWMwYWNcdWQ2OGNcdWM4MDFcdWM1NTVcdWI4MjVcdWFjZmMgXHVjMmUwXHVkMWI1XHViODI1LCBcdWIzZDlcdWM2ZDBcdWI4MjVcdWFjZmMgXHVhYzAwXHVkNjM4XHViODI1LCBcdWIyZTRcdWI4MjVcdWFjZmMgXHViMzAwXHViODI1LCBcdWFjMTBcdWFjMDFcdWI4MjVcdWFjZmMgXHVhYzEwXHViNGRkXHViODI1LCBcdWM3OTBcdWFlMzBcdWMxMzhcdWI4MjVcdWFjZmMgXHVjNzdjXHVjMmVjXHVkNjExXHViODI1LCBcdWM3NzRcdWM5ZDFcdWQyYjhcdWI4MjVcdWFjZmMgXHVjODE1XHVjOWMwXHViOWM4XHVjYzMwXHViODI1LCBcdWM3YTBcdWM3YWNcdWFkNmNcdWI5ZTRcdWI4MjVcdWFjZmMgXHVjZDVjXHViMzAwXHViOWM4XHVjYzMwXHViODI1LCBcdWFjMTBcdWMwYzFcdWI4MjVcdWFjZmMgXHVhYzFjXHVhZDA0XHViODI1LCBcdWFjMWNcdWJjMWNcdWI4MjVcdWFjZmMgXHVhYzFjXHViMTUwXHViODI1LCBcdWIzYzRcdWI4MjVcdWFjZmMgXHVhZDZjXHVjMGMxXHViODI1LCBcdWFkMDBcdWQxYjVcdWI4MjVcdWFjZmMgXHViYjNjXHViODI1LCBcdWFlMzBcdWM4NzBcdWI4MjVcdWFjZmMgXHVhZTMwXHVjODA0XHViODI1LCBcdWIyZjRcdWMxMzhcdWI4MjVcdWFjZmMgXHViM2M1XHVjMTFjXHViODI1LCBcdWIzYzVcdWNjM2RcdWI4MjVcdWFjZmMgXHViYzk1XHViODI1XHVjNzQ0IFx1YWUzMFx1Yjk3NFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjN2FjXHViYmY4XHVjNzg4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0IFx1ZDU1YyBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmNmNFx1YjRkY1x1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuIFx1Yzc3NCBcdWJjZjRcdWI0ZGNcdWIyOTQgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBOKk5cdWFjMWNcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0IFx1YmUxNFx1Yjg1ZFx1YjNjNCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQwIFx1Yzc3NCBcdWJlMTRcdWI4NWRcdWM3NDQgXHViY2Y0XHViNGRjIFx1YzcwNFx1Yzc1OCBcdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YzcwNFx1YzVkMCBcdWM2MmNcdWI4MjRcdWIxOTNcdWFjNzBcdWIwOTgsIFx1YjJlNFx1Yjk3OCBcdWJlMTRcdWI4NWQgXHVjNzA0XHVjNWQwIFx1YzYyY1x1YjgyNCBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWJlMTRcdWI4NWRcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjMDBcdWI0ZGQgXHVjYzQ0XHVjNmIwXHVhYzhjIFx1YjE5M1x1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWM3NzQgXHViMTgwXHVjNzc0XHViOTdjIFx1ZDU1OFx1YWNlMCBcdWIwOWMgXHViMmU0XHVjNzRjXHVjNWQwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWI0YjdcdWM4MTVcdWI5YWNcdWI5N2MgXHVkNTU4XHVhY2UwIFx1YzlkMVx1YzVkMCBcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YjRiN1x1YzgxNVx1YjlhY1x1Yjk3YyBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJiZmNcdWQ2MDEgXHVjMTIwXHVjMGRkXHViMmQ4XHVhY2ZjIFx1YjgyNVx1YzczY1x1Yjg1YyBcdWIwNWRcdWIwOThcdWIyOTQgXHViMmU4XHVjNWI0IFx1YzY3OFx1YzZiMFx1YWUzMFx1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVjNTQ0XHVjNzc0XHViNGU0XHVjNWQwXHVhYzhjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNjZDAgXHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHViZTE0XHViODVkXHVjNzQ0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHViYzMwXHVjNWY0XHVkNTU4XHViNzdjXHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQ1NWMgXHViZTE0XHViODVkIFx1YzcwNFx1YzVkMCBcdWIyZTRcdWI5NzggXHViZTE0XHViODVkXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzljMFx1YWUwOCBcdWJlMTRcdWI4NWRcdWM3NTggXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWJlMTRcdWI4NWRcdWM3NzQgXHViMTkzXHVjNzc4IFx1YmFhOFx1YzJiNVx1Yzc3NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViNDE4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViZTE0XHViODVkXHVjNzQ0IFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHVhYzFjIFx1YzZjMFx1YzljMVx1YzVlY1x1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1ZDU1YyBcdWNlNzhcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViZTE0XHViODVkXHVjNzQ0IFx1YjJlNFx1Yjk3OCBcdWNlNzhcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWM2MmNcdWI4MjRcdWIxOTNcdWIyOTQgXHVjNzc0XHViM2Q5XHViOWNjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjZjRcdWI0ZGNcdWQzMTBcdWM3NTggXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzQgTlx1YWNmYyBcdWFkZjggXHVjNzA0XHVjNzU4IFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IE0gJmxlOyBOPHN1cD4yPFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4KFx1Yzg4Y1x1ZDQ1YykgUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBSLCBDICZsZTsgTik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YWMxYyBcdWM3NzRcdWIzZDlcdWMyZGNcdWQwYTRcdWJhNzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0KDIsIDMpXHVjNzQ0ICgzLCAzKVx1YzczY1x1Yjg1YywgKDQsIDIpXHViOTdjICgyLCA1KVx1Yjg1YywgKDQsIDQpXHViOTdjICgzLCA1KVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWMyZGNcdWQwYTRcdWJhNzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5MzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJORVJFRCIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIG5lYXJieSBraW5kZXJnYXJ0ZW4gdGhleSByZWNlbnRseSBtYWRlIHVwIGFuIGF0dHJhY3RpdmUgZ2FtZSBvZiBzdHJlbmd0aCBhbmQgYWdpbGl0eSB0aGF0IGtpZHMgbG92ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHN1cmZhY2UgZm9yIHRoZSBnYW1lIGlzIGEgbGFyZ2UgZmxhdCBhcmVhIGRpdmlkZWQgaW50byBOJnRpbWVzO04gc3F1YXJlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNoaWxkcmVuIGxheSBsYXJnZSBzcG9uZ3kgY3VlcyBvbnRvIHRoZSBzdXJmYWNlLiBUaGUgc2lkZXMgb2YgdGhlIGN1YmVzIGFyZSB0aGUgc2FtZSBsZW5ndGggYXMgdGhlIHNpZGVzIG9mIHRoZSBzcXVhcmVzLiBXaGVuIGEgY3ViZSBpcyBwdXQgb24gdGhlIHN1cmZhY2UsIGl0cyBzaWRlcyBhcmUgYWxpZ25lZCB3aXRoIHNvbWUgc3F1YXJlLiBBIGN1YmUgbWF5IGJlIHB1dCBvbiBhbm90aGVyIGN1YmUgdG9vLiZuYnNwOzxcL3A+XHJcblxyXG48cD5LaWRzIGVuam95IGJ1aWxkaW5nIGZvcnRzIGFuZCBoaWRpbmcgdGhlbSwgYnV0IHRoZXkgYWx3YXlzIGxlYXZlIGJlaGluZCBhIGh1Z2UgbWVzcy4gQmVjYXVzZSBvZiB0aGlzLCBwcmlvciB0byBjbG9zaW5nIHRoZSBraW5kZXJnYXJ0ZW4sIHRoZSB0ZWFjaGVycyByZWFycmFuZ2UgYWxsIHRoZSBjdWJlcyBzbyB0aGF0IHRoZXkgb2NjdXB5IGEgcmVjdGFuZ2xlIG9uIHRoZSBzdXJmYWNlLCB3aXRoIGV4YWN0bHkgb25lIGN1YmUgb24gZXZlcnkgc3F1YXJlIGluIHRoZSByZWN0YW5nbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG9uZSBtb3ZpbmcsIGEgY3ViZSBpcyB0YWtlbiBvZmYgdGhlIHRvcCBvZiBhIHNxdWFyZSB0byB0aGUgdG9wIG9mIGFueSBvdGhlciBzcXVhcmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgc3RhdGUgb2YgdGhlIHN1cmZhY2UsIGNhbGN1bGF0ZXMgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBtb3ZlcyBuZWVkZWQgdG8gYXJyYW5nZSBhbGwgY3ViZXMgaW50byBhIHJlY3RhbmdsZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IE0gJmxlOyBOPHN1cD4yPFwvc3VwPiksIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBzdXJmYWNlIGFuZCB0aGUgbnVtYmVyIG9mIGN1YmVzIGN1cnJlbnRseSBvbiB0aGUgc3VyZmFjZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMgKDEgJmxlOyBSLCBDICZsZTsgTiksIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgc3F1YXJlIHRoYXQgY29udGFpbnMgdGhlIGN1YmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgbW92ZXMuIEEgc29sdXRpb24gd2lsbCBhbHdheXMgZXhpc3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #6 3번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: doju