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

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3 2
1 1
1 1

예제 출력 1

1

예제 입력 2

4 3
2 2
4 4
1 1

예제 출력 2

2

예제 입력 3

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

예제 출력 3

3

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

W3sicHJvYmxlbV9pZCI6IjI5MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI4NWQgXHVjODE1XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZmNcdWQ2MDEgXHVjNzIwXHVjZTU4XHVjNmQwXHVjNWQwXHVjMTFjXHViMjk0IFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWNjM2RcdWM3NThcdWI4MjVcdWFjZmMgXHVjNzc4XHViMGI0XHViODI1LCBcdWFkZmNcdWI4MjVcdWFjZmMgXHVjOWMwXHVhZDZjXHViODI1LCBcdWM3ODlcdWM1ZWNcdWI4MjVcdWFjZmMgXHVkMGM0XHVjMTMxXHViODI1LCBcdWQzMTBcdWIyZThcdWI4MjVcdWFjZmMgXHViMTc4XHViODI1LCBcdWFlMzBcdWI4MjVcdWFjZmMgXHVkNjVjXHViM2Q5XHViODI1LCBcdWQ2NWNcdWI4MjVcdWFjZmMgXHViMmVjXHViODI1LCBcdWIwYjRcdWFkNmNcdWI4MjVcdWFjZmMgXHViY2MwXHVkNjE1XHViODI1LCBcdWM3NTFcdWM5ZDFcdWI4MjVcdWFjZmMgXHViYjM0XHViODI1LCBcdWM5YzBcdWI4MjVcdWFjZmMgXHViOWU0XHViODI1LCBcdWJiZjhcdWI4MjVcdWFjZmMgXHViMmY0XHViODI1LCBcdWIyYTVcdWI4MjVcdWFjZmMgXHVjMmU0XHViODI1LCBcdWM1NTVcdWI4MjVcdWFjZmMgXHVkNjExXHViODI1LCBcdWNjYjRcdWI4MjVcdWFjZmMgXHVhY2JkXHViODI1LCBcdWQzZWRcdWI4MjVcdWFjZmMgXHVjMTM4XHViODI1LCBcdWM1OTFcdWI4MjVcdWFjZmMgXHVjNzRjXHViODI1LCBcdWM3ODVcdWI4MjVcdWFjZmMgXHVjZDljXHViODI1LCBcdWFkOGNcdWI4MjVcdWFjZmMgXHVjOGZjXHViODI1LCBcdWJjZDFcdWI4MjVcdWFjZmMgXHVjODA0XHViODI1LCBcdWI5YzhcdWNjMzBcdWI4MjVcdWFjZmMgXHViM2Q5XHViODI1LCBcdWM4MDRcdWFlMzBcdWI4MjVcdWFjZmMgXHVkNmE4XHViODI1LCBcdWIwYjRcdWI4MjVcdWFjZmMgXHVhZDZkXHViODI1LCBcdWM3OTBcdWFlMzBcdWI4MjVcdWFjZmMgXHVjOTExXHViODI1LCBcdWQ2NTRcdWI4MjVcdWFjZmMgXHVjMjE4XHViODI1LCBcdWM2ZDBcdWM3OTBcdWI4MjVcdWFjZmMgXHVjNjAxXHVkNWE1XHViODI1LCBcdWM3NzRcdWI4MjVcdWFjZmMgXHVhY2JkXHVjN2MxXHViODI1LCBcdWFjYmRcdWM4MWNcdWI4MjVcdWFjZmMgXHVjMTI0XHViNGRkXHViODI1LCBcdWFjZjVcdWFkOGNcdWI4MjVcdWFjZmMgXHVjNmQwXHViM2Q5XHViODI1LCBcdWM4MTVcdWNlNThcdWI4MjVcdWFjZmMgXHVjOWQxXHVjOTExXHViODI1LCBcdWNkOTRcdWM5YzRcdWI4MjVcdWFjZmMgXHVjNWYwXHVhZTMwXHViODI1LCBcdWM3YTBcdWM3YWNcdWI4MjVcdWFjZmMgXHVjODE1XHVjMmUwXHViODI1LCBcdWJkODBcdWI4MjVcdWFjZmMgXHVjN2FjXHViODI1LCBcdWI5YzhcdWI4MjVcdWFjZmMgXHVjNzIwXHViODI1LCBcdWM4NzBcdWI4MjVcdWFjZmMgXHVjNWVjXHViODI1LCBcdWNkMDhcdWIyYTVcdWI4MjVcdWFjZmMgXHVjNjA4XHVjOWMwXHViODI1LCBcdWQ0NWNcdWQ2MDRcdWI4MjVcdWFjZmMgXHVhZTMwXHVjNWI1XHViODI1LCBcdWJiMzRcdWFlMzBcdWI4MjVcdWFjZmMgXHVjYzNkXHVjODcwXHViODI1LCBcdWMyMWNcdWJjMWNcdWI4MjVcdWFjZmMgXHVjODAwXHVkNTZkXHViODI1LCBcdWQ2MzhcdWMxOGNcdWI4MjVcdWFjZmMgXHVhZDAwXHVjYzMwXHViODI1LCBcdWFkNmNcdWMxOGRcdWI4MjVcdWFjZmMgXHVkNDhkXHViODI1LCBcdWNjYWRcdWI4MjVcdWFjZmMgXHVjMmRjXHViODI1LCBcdWQ1NTlcdWI4MjVcdWFjZmMgXHVkNTQ0XHViODI1LCBcdWM2NDRcdWI4MjVcdWFjZmMgXHVjMGFjXHViODI1LCBcdWMyMThcdWMwYWNcdWI4MjVcdWFjZmMgXHVjNzkwXHVjMGRkXHViODI1LCBcdWFjZTBcdWQ1NTlcdWI4MjVcdWFjZmMgXHViYzg4XHVjMmRkXHViODI1LCBcdWM3OTBcdWFlMDhcdWI4MjVcdWFjZmMgXHVkM2VjXHVjNmE5XHViODI1LCBcdWM4MTVcdWI4MjVcdWFjZmMgXHVkM2I4XHViODI1LCBcdWMxOGRcdWI4MjVcdWFjZmMgXHVkNTNjXHViODI1LCBcdWM5YzBcdWIzYzRcdWI4MjVcdWFjZmMgXHVkMWI1XHVjODFjXHViODI1LCBcdWFlMzBcdWIzZDlcdWI4MjVcdWFjZmMgXHVjMGFjXHVhY2UwXHViODI1LCBcdWJiMzRcdWM5MTFcdWI4MjVcdWFjZmMgXHVhY2IwXHVjODE1XHViODI1LCBcdWM3NzRcdWQ1NzRcdWI4MjVcdWFjZmMgXHVjZTVjXHVkNjU0XHViODI1LCBcdWFjYjBcdWIyZThcdWI4MjVcdWFjZmMgXHVkMGRjXHVjNTkxXHViODI1LCBcdWFjZjVcdWFjYTlcdWI4MjVcdWFjZmMgXHViYzI5XHVjNWI0XHViODI1LCBcdWIzY2NcdWQzMGNcdWI4MjVcdWFjZmMgXHVjN2E1XHVjNTQ1XHViODI1LCBcdWM4MDRcdWMxOGRcdWI4MjVcdWFjZmMgXHVkNzYxXHVjNzc4XHViODI1LCBcdWFkMzRcdWI4MjVcdWFjZmMgXHVhZGY5XHViODI1LCBcdWIzYzVcdWI4MjVcdWFjZmMgXHVhY2JkXHVhZTMwXHViODI1LCBcdWFlMzBcdWQ2OGRcdWI4MjVcdWFjZmMgXHViNGRkXHVjODEwXHViODI1LCBcdWM4MDFcdWM3NTFcdWI4MjVcdWFjZmMgXHVkMzBjXHVhZDM0XHViODI1LCBcdWQ1ODlcdWM4MTVcdWI4MjVcdWFjZmMgXHVhZDZjXHViOWU0XHViODI1LCBcdWIzYzRcdWM1N2RcdWI4MjVcdWFjZmMgXHViYzE4XHViYzFjXHViODI1LCBcdWM5YzRcdWI4MjVcdWFjZmMgXHVhZTA4XHViODI1LCBcdWFjMTVcdWI4MjVcdWFjZmMgXHVjNTdkXHViODI1LCBcdWM4MTVcdWNlNThcdWFkOGNcdWI4MjVcdWFjZmMgXHViZDg0XHVjMTFkXHViODI1LCBcdWMxMzhcdWM4MTVcdWI4MjVcdWFjZmMgXHVjNzkwXHVjODFjXHViODI1LCBcdWJjMThcdWM3OTFcdWM2YTlcdWI4MjVcdWFjZmMgXHViOWNjXHVjNzIwXHVjNzc4XHViODI1LCBcdWFkZmNcdWM5YzBcdWFkNmNcdWI4MjVcdWFjZmMgXHVjOWM0XHVjMmVjXHVjODA0XHViODI1LCBcdWJkODhcdWFjMDBcdWQ1NmRcdWI4MjVcdWFjZmMgXHVjY2FkXHVjYzljXHViY2JkXHViODI1LCBcdWQzZWRcdWJjMWNcdWI4MjVcdWFjZmMgXHVkNjE1XHVjMTMxXHViODI1LCBcdWFjYWNcdWM4MWNcdWI4MjVcdWFjZmMgXHVjN2E1XHViODI1LCBcdWFjMDFcdWI4MjVcdWFjZmMgXHVhYzEwXHVkNTZkXHViMmE1XHViODI1LCBcdWFjYjhcdWM3NzhcdWM5YzBcdWI4MjVcdWFjZmMgXHVhY2IwXHVjMmVjXHVjNzIxXHViODI1LCBcdWFjZTBcdWFkMTFcdWM5YzBcdWI4MjVcdWFjZmMgXHVhZDZjXHVjMGFjXHViODI1LCBcdWIyZThcdWFjYjBcdWI4MjVcdWFjZmMgXHVjMGRkXHVkNjVjXHViODI1LCBcdWMyMThcdWJlNDRcdWI4MjVcdWFjZmMgXHVjNmI0XHViM2Q5XHViODI1LCBcdWFkNTBcdWM4MTVcdWMyZGNcdWI4MjVcdWFjZmMgXHVhY2Y1XHViODI1LCBcdWM1YjRcdWQ3MThcdWI4MjVcdWFjZmMgXHVhZDcwXHVjYzQ1XHVhZDcwXHViODI1LCBcdWFkNmNcdWQwZGNcdWM1OTFcdWI4MjVcdWFjZmMgXHVjODcwXHVjOWMxXHViODI1LCBcdWFjMDBcdWNjM2RcdWI4MjVcdWFjZmMgXHViYjM4XHVjN2E1XHViODI1LCBcdWJjMWNcdWQ0NWNcdWI4MjVcdWFjZmMgXHVhZDUwXHViODI1LCBcdWFkODFcdWI4MjVcdWFjZmMgXHViM2Q5XHVjMmVjXHVkNTY5XHViODI1LCBcdWJjMjlcdWM3MDRcdWI4MjVcdWFjZmMgXHVjMThjXHViZTQ0XHViODI1LCBcdWM1ZjBcdWNkOWNcdWI4MjVcdWFjZmMgXHVjNzkwXHViY2Y4XHViODI1LCBcdWM4ZmNcdWIzYzRcdWI4MjVcdWFjZmMgXHVhZGY4XHViODA4XHVhY2UwXHViOWFjXHViODI1LCBcdWM3MjhcdWI5YWNcdWM2YjBcdWMyYTRcdWI4MjVcdWFjZmMgXHViOWM4XHVkNjM4XHViYTU0XHVkMmI4XHViODI1LCBcdWJiMzRcdWIyYTVcdWI4MjVcdWFjZmMgXHVjNzkxXHVjNmE5XHViODI1LCBcdWM4ZmNcdWIzZDlcdWI4MjVcdWFjZmMgXHVhYzAwXHViODVjXHViY2Y1XHVjNmQwXHViODI1LCBcdWFjMTVcdWM4MWNcdWQxYjVcdWM2MDFcdWI4MjVcdWFjZmMgXHVhYzhjXHVjNzc0XHVjOWMwXHVjNTU1XHViODI1LCBcdWFjYmRcdWM4MWNcdWM3YTBcdWM3YWNcdWI4MjVcdWFjZmMgXHViZDg0XHVkMjJjXHViMTc4XHViODI1LCBcdWFjZjVcdWMxOGNcdWM3NThcdWQ2YThcdWI4MjVcdWFjZmMgXHViZDg4XHVjNzIwXHVjNWVjXHViODI1LCBcdWM5YzFcdWFjMTBcdWI4MjVcdWFjZmMgXHVjOWMxXHVhZDAwXHViODI1LCBcdWNkOTRcdWI5YWNcdWI4MjVcdWFjZmMgXHVjZGE5XHVhY2E5XHViODI1LCBcdWQ2YTFcdWM1NTVcdWI4MjVcdWFjZmMgXHVhYzEwXHViY2M0XHViODI1LCBcdWFjYjBcdWQ1NjlcdWI4MjVcdWFjZmMgXHVhZTMwXHVjMjIwXHViODI1LCBcdWJiZjhcdWM4MDFcdWQzMTBcdWIyZThcdWI4MjVcdWFjZmMgXHViYzFjXHVjODA0XHVjMThjXHVjZDljXHViODI1LCBcdWMwYWNcdWQ2OGNcdWM4MDFcdWM1NTVcdWI4MjVcdWFjZmMgXHVjMmUwXHVkMWI1XHViODI1LCBcdWIzZDlcdWM2ZDBcdWI4MjVcdWFjZmMgXHVhYzAwXHVkNjM4XHViODI1LCBcdWIyZTRcdWI4MjVcdWFjZmMgXHViMzAwXHViODI1LCBcdWFjMTBcdWFjMDFcdWI4MjVcdWFjZmMgXHVhYzEwXHViNGRkXHViODI1LCBcdWM3OTBcdWFlMzBcdWMxMzhcdWI4MjVcdWFjZmMgXHVjNzdjXHVjMmVjXHVkNjExXHViODI1LCBcdWM3NzRcdWM5ZDFcdWQyYjhcdWI4MjVcdWFjZmMgXHVjODE1XHVjOWMwXHViOWM4XHVjYzMwXHViODI1LCBcdWM3YTBcdWM3YWNcdWFkNmNcdWI5ZTRcdWI4MjVcdWFjZmMgXHVjZDVjXHViMzAwXHViOWM4XHVjYzMwXHViODI1LCBcdWFjMTBcdWMwYzFcdWI4MjVcdWFjZmMgXHVhYzFjXHVhZDA0XHViODI1LCBcdWFjMWNcdWJjMWNcdWI4MjVcdWFjZmMgXHVhYzFjXHViMTUwXHViODI1LCBcdWIzYzRcdWI4MjVcdWFjZmMgXHVhZDZjXHVjMGMxXHViODI1LCBcdWFkMDBcdWQxYjVcdWI4MjVcdWFjZmMgXHViYjNjXHViODI1LCBcdWFlMzBcdWM4NzBcdWI4MjVcdWFjZmMgXHVhZTMwXHVjODA0XHViODI1LCBcdWIyZjRcdWMxMzhcdWI4MjVcdWFjZmMgXHViM2M1XHVjMTFjXHViODI1LCBcdWIzYzVcdWNjM2RcdWI4MjVcdWFjZmMgXHViYzk1XHViODI1LCBcdWFjMTVcdWQ1NWNcdWQ1NzVcdWI4MjVcdWFjZmMgXHVjNTdkXHVkNTVjXHVkNTc1XHViODI1XHVjNzQ0IFx1YWUzMFx1Yjk3NFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjN2FjXHViYmY4XHVjNzg4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0IFx1ZDU1YyBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmNmNFx1YjRkY1x1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuIFx1Yzc3NCBcdWJjZjRcdWI0ZGNcdWIyOTQgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBOKk5cdWFjMWNcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0IFx1YmUxNFx1Yjg1ZFx1YjNjNCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQwIFx1Yzc3NCBcdWJlMTRcdWI4NWRcdWM3NDQgXHViY2Y0XHViNGRjIFx1YzcwNFx1Yzc1OCBcdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YzcwNFx1YzVkMCBcdWM2MmNcdWI4MjRcdWIxOTNcdWFjNzBcdWIwOTgsIFx1YjJlNFx1Yjk3OCBcdWJlMTRcdWI4NWQgXHVjNzA0XHVjNWQwIFx1YzYyY1x1YjgyNCBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWJlMTRcdWI4NWRcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjMDBcdWI0ZGQgXHVjYzQ0XHVjNmIwXHVhYzhjIFx1YjE5M1x1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWM3NzQgXHViMTgwXHVjNzc0XHViOTdjIFx1ZDU1OFx1YWNlMCBcdWIwOWMgXHViMmU0XHVjNzRjXHVjNWQwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWI0YjdcdWM4MTVcdWI5YWNcdWI5N2MgXHVkNTU4XHVhY2UwIFx1YzlkMVx1YzVkMCBcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YjRiN1x1YzgxNVx1YjlhY1x1Yjk3YyBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJiZmNcdWQ2MDEgXHVjMTIwXHVjMGRkXHViMmQ4XHVhY2ZjIFx1YjgyNVx1YzczY1x1Yjg1YyBcdWIwNWRcdWIwOThcdWIyOTQgXHViMmU4XHVjNWI0IFx1YzY3OFx1YzZiMFx1YWUzMFx1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVjNTQ0XHVjNzc0XHViNGU0XHVjNWQwXHVhYzhjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNjZDAgXHVjOGZjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHViZTE0XHViODVkXHVjNzQ0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHViYzMwXHVjNWY0XHVkNTU4XHViNzdjXHVhY2UwIFx1ZDU4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQ1NWMgXHViZTE0XHViODVkIFx1YzcwNFx1YzVkMCBcdWIyZTRcdWI5NzggXHViZTE0XHViODVkXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWFlMDggXHViZTE0XHViODVkXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHViZTE0XHViODVkXHVjNzc0IFx1YjE5M1x1Yzc3OCBcdWJhYThcdWMyYjVcdWM3NzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YjQxOFx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YWMxYyBcdWM2YzBcdWM5YzFcdWM1ZWNcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWQ1NWMgXHVjZTc4XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWIyZTRcdWI5NzggXHVjZTc4XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDAgXHVjNjJjXHViODI0XHViMTkzXHViMjk0IFx1Yzc3NFx1YjNkOVx1YjljYyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2Y0XHViNGRjXHVkMzEwXHVjNzU4IFx1ZDU1YyBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWFjZmMgXHVhZGY4IFx1YzcwNFx1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsIDEgJmxlOyBNICZsZTsgTjxzdXA+MjxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OChcdWM4OGNcdWQ0NWMpIFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUiwgQyAmbGU7IE4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWFjMWMgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGE0XHViYTc0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPigyLCAzKVx1Yzc0NCAoMywgMylcdWM3M2NcdWI4NWMsICg0LCAyKVx1Yjk3YyAoMiwgNSlcdWI4NWMsICg0LCA0KVx1Yjk3YyAoMywgNSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGE0XHViYTc0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjkzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5FUkVEIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgbmVhcmJ5IGtpbmRlcmdhcnRlbiB0aGV5IHJlY2VudGx5IG1hZGUgdXAgYW4gYXR0cmFjdGl2ZSBnYW1lIG9mIHN0cmVuZ3RoIGFuZCBhZ2lsaXR5IHRoYXQga2lkcyBsb3ZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc3VyZmFjZSBmb3IgdGhlIGdhbWUgaXMgYSBsYXJnZSBmbGF0IGFyZWEgZGl2aWRlZCBpbnRvIE4mdGltZXM7TiBzcXVhcmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY2hpbGRyZW4gbGF5IGxhcmdlIHNwb25neSBjdWVzIG9udG8gdGhlIHN1cmZhY2UuIFRoZSBzaWRlcyBvZiB0aGUgY3ViZXMgYXJlIHRoZSBzYW1lIGxlbmd0aCBhcyB0aGUgc2lkZXMgb2YgdGhlIHNxdWFyZXMuIFdoZW4gYSBjdWJlIGlzIHB1dCBvbiB0aGUgc3VyZmFjZSwgaXRzIHNpZGVzIGFyZSBhbGlnbmVkIHdpdGggc29tZSBzcXVhcmUuIEEgY3ViZSBtYXkgYmUgcHV0IG9uIGFub3RoZXIgY3ViZSB0b28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPktpZHMgZW5qb3kgYnVpbGRpbmcgZm9ydHMgYW5kIGhpZGluZyB0aGVtLCBidXQgdGhleSBhbHdheXMgbGVhdmUgYmVoaW5kIGEgaHVnZSBtZXNzLiBCZWNhdXNlIG9mIHRoaXMsIHByaW9yIHRvIGNsb3NpbmcgdGhlIGtpbmRlcmdhcnRlbiwgdGhlIHRlYWNoZXJzIHJlYXJyYW5nZSBhbGwgdGhlIGN1YmVzIHNvIHRoYXQgdGhleSBvY2N1cHkgYSByZWN0YW5nbGUgb24gdGhlIHN1cmZhY2UsIHdpdGggZXhhY3RseSBvbmUgY3ViZSBvbiBldmVyeSBzcXVhcmUgaW4gdGhlIHJlY3RhbmdsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gb25lIG1vdmluZywgYSBjdWJlIGlzIHRha2VuIG9mZiB0aGUgdG9wIG9mIGEgc3F1YXJlIHRvIHRoZSB0b3Agb2YgYW55IG90aGVyIHNxdWFyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBzdGF0ZSBvZiB0aGUgc3VyZmFjZSwgY2FsY3VsYXRlcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIG1vdmVzIG5lZWRlZCB0byBhcnJhbmdlIGFsbCBjdWJlcyBpbnRvIGEgcmVjdGFuZ2xlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXJzIE4gYW5kIE0gKDEgJmxlOyBOICZsZTsgMTAwLCAxICZsZTsgTSAmbGU7IE48c3VwPjI8XC9zdXA+KSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHN1cmZhY2UgYW5kIHRoZSBudW1iZXIgb2YgY3ViZXMgY3VycmVudGx5IG9uIHRoZSBzdXJmYWNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQyAoMSAmbGU7IFIsIEMgJmxlOyBOKSwgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBzcXVhcmUgdGhhdCBjb250YWlucyB0aGUgY3ViZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBtb3Zlcy4gQSBzb2x1dGlvbiB3aWxsIGFsd2F5cyBleGlzdC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0IGV4YW1wbGUsIGl0IHN1ZmZpY2VzIHRvIG1vdmUgb25lIG9mIHRoZSBjdWJlcyBmcm9tICgxLCAxKSB0byAoMSwgMikgb3IgKDIsIDEpLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgdGhpcmQgZXhhbXBsZSwgYSBjdWJlIGlzIG1vdmVkIGZyb20gKDIsIDMpIHRvICgzLCAzKSwgZnJvbSAoNCwgMikgdG8gKDIsIDUpIGFuZCBmcm9tICg0LCA0KSB0byAoMywgNSkuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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