시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 61 19 17 34.000%

문제

다솜이는 눈이 오늘 날 아침이면 어김없이 테라스에 나가 발자국을 남기는 것이 취미다. 하지만 늦게 일어나는 조교는 단지 발자국만을 보며 추측할 수 밖에 없다. 그러던 어느 날 아침에 조교는 다솜이의 발자취가 궁금해졌다. 하지만 이미 너무 많은 학생들이 왔다 갔다 했기에 발자취를 찾기란 쉬운 일이 아니었다.
  한 가지 확실한 점은 학생들은 언제나 일직선으로 이동하며 눈을 밟으며 걸음폭도 일정하다는 것이다.


  위의 그림과 같이 다솜이를 포함한 학생들의 발자취는 뛰는 간격이나 방향이 서로 제각각일 수 있다.

위의 그림에서와 같이 학생들은 밖에서부터 일직선으로 들어와 정확한 보폭으로 눈을 밟고 지나간다.

그림 3과 같이 아침에 여러 학생들은 제각기 다른 방향에서 들어와 서로 다른 방향으로 밟고 지나간다. 물론 여러 명이 한 곳을 밟을 수도 있다. 그리고 늦잠을 잔 조교는 그림 4와 같이 밟고 지나간 최종 상태만 볼 수 있다.
  그림 4를 보면, 학생들이 몇 명 들어 와서 어느 방향으로 어느 간격으로 눈 위에 발자국을 내고 갔는지 그 경로를 재현할 수 있다. 단, 세 번 이상 눈 위에 발자국을 낸 학생의 경로만 생각하기로 한다. 그렇다면, 그림 4의 상황이라면 그림 3과 같은 세 개의 학생 경로가 있다고 말할 수 있다. (물론 다른 가짓수도 있을 수 있다.)

한편, 첫째 칸에서 수직으로 내려가는 경로는 보폭이 4인 학생의 경로일 수도 있지만, 이 경로는 총 발자국이 두 개이기 때문에 고려하지 않는다. 그리고 둘째 줄 셋째 칸(2, 3), 셋째 줄 넷째 칸(3, 4), 여섯째 줄 일곱째(6, 7) 칸을 지나는 경로는 일직선이고 세 개의 발자국을 남겼지만, 간격이 일정하지 않기 때문에 한 학생이 밟고 간 경로로 인정하지 않는다.

어떤 학생이 밟고 간 경로에 속하는 선상에 다른 학생이 밟고 간 곳이 있을 수 있다. 예를 들어 위 그림에서 (2, 1), (2, 3), (2, 5), (2, 7)은 한 학생이 밟고 간 경로인데, 이 선 안에는 (2, 6)처럼 다른 학생이 밟고 간 곳이 있을 수 있다. 그리고 사실은, 발자국이 있지만 이번에 학생이 남긴게 아닌 이 전에 눈이 왔을 때 남은 발자국일 수도 있다

세상에서 제일 착한 다솜이는 가장 많은 발자국을 남기고 지나가기에 이를 찾는 것이 문제이다. 그림 4의 경우, 정답은 7이다. 여섯째 줄부터 가로로 일곱 발자국을 모두 밟고 지나간 학생을 다솜이로 추정할 수 있기 때문이다.

입력

첫째 줄에는 테라스의 세로, 가로 크기를 나타내는 정수 R과 C(1≤R, C≤5000)가 있다. 그리고 둘째 줄에는 학생들의 발자국 수 N(3≤N≤5000)이 있다.  그리고 다음 N 줄에는 발자국이 있는 좌표를 나타내는 정수 두 개가 뒤따른다. 처음 것이 줄(세로) 좌표이고 나중 것이 칸(가로) 좌표이다. (1≤줄 좌표≤R, 1≤칸 좌표≤C) 두 정수는 공백 한 칸으로 구분된다. 여러 학생에게 밟혔더라도 좌표는 한 번만 나온다.

출력

다솜이로 추정되는 가장 많은 발자국을 남기고 간 학생의 발자국 수를 출력한다. 만약 학생의 경로를 하나도 발견하지 못했다면 그냥 0을 출력한다.

예제 입력 1

6 7       
14
2 1
6 6
4 2
2 5
2 6
2 7
3 4
6 1
6 2
2 3
6 3
6 4
6 5
6 7

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjE3NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzhcdWMwYzFcdWM1ZDBcdWMxMWMgXHVjODFjXHVjNzdjIFx1Y2MyOVx1ZDU1YyBcdWIyZTRcdWMxOWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1YzE5Y1x1Yzc3NFx1YjI5NCBcdWIyMDhcdWM3NzQgXHVjNjI0XHViMjk4IFx1YjBhMCBcdWM1NDRcdWNlNjhcdWM3NzRcdWJhNzQgXHVjNWI0XHVhZTQwXHVjNWM2XHVjNzc0IFx1ZDE0Y1x1Yjc3Y1x1YzJhNFx1YzVkMCBcdWIwOThcdWFjMDAgXHViYzFjXHVjNzkwXHVhZDZkXHVjNzQ0IFx1YjBhOFx1YWUzMFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjZGU4XHViYmY4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViMmE2XHVhYzhjIFx1Yzc3Y1x1YzViNFx1YjA5OFx1YjI5NCBcdWM4NzBcdWFkNTBcdWIyOTQgXHViMmU4XHVjOWMwIFx1YmMxY1x1Yzc5MFx1YWQ2ZFx1YjljY1x1Yzc0NCBcdWJjZjRcdWJhNzAgXHVjZDk0XHVjZTIxXHVkNTYwIFx1YzIxOCBcdWJjMTZcdWM1ZDAgXHVjNWM2XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIzNTggXHVjNWI0XHViMjkwIFx1YjBhMCBcdWM1NDRcdWNlNjhcdWM1ZDAgXHVjODcwXHVhZDUwXHViMjk0IFx1YjJlNFx1YzE5Y1x1Yzc3NFx1Yzc1OCBcdWJjMWNcdWM3OTBcdWNkZThcdWFjMDAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzc0XHViYmY4IFx1YjEwOFx1YmIzNCBcdWI5Y2VcdWM3NDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzY1NFx1YjJlNCBcdWFjMTRcdWIyZTQgXHVkNTg4XHVhZTMwXHVjNWQwIFx1YmMxY1x1Yzc5MFx1Y2RlOFx1Yjk3YyBcdWNjM2VcdWFlMzBcdWI3ODAgXHVjMjZjXHVjNmI0IFx1Yzc3Y1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWM1YzhcdWIyZTQuIDxiciBcLz5cclxuJm5ic3A7IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVkNjU1XHVjMmU0XHVkNTVjIFx1YzgxMFx1Yzc0MCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjNWI4XHVjODFjXHViMDk4IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzAgXHViMjA4XHVjNzQ0IFx1YmMxZlx1YzczY1x1YmE3MCBcdWFjNzhcdWM3NGNcdWQzZWRcdWIzYzQgXHVjNzdjXHVjODE1XHVkNTU4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjc4XCIgaGVpZ2h0PVwiMTMwXCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL3BpYzEuUE5HXCIgXC8+PFwvcD5cclxuPHA+PGJyIFwvPlxyXG4mbmJzcDsgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViMmU0XHVjMTljXHVjNzc0XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHViYzFjXHVjNzkwXHVjZGU4XHViMjk0IFx1YjZmMFx1YjI5NCBcdWFjMDRcdWFjYTlcdWM3NzRcdWIwOTggXHViYzI5XHVkNWE1XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM4MWNcdWFjMDFcdWFjMDFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjE1XCIgaGVpZ2h0PVwiMTYxXCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL3BpYzIuUE5HXCIgXC8+PFwvcD5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExY1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YmMxNlx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWM3N2NcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjQwIFx1YzgxNVx1ZDY1NVx1ZDU1YyBcdWJjZjRcdWQzZWRcdWM3M2NcdWI4NWMgXHViMjA4XHVjNzQ0IFx1YmMxZlx1YWNlMCBcdWM5YzBcdWIwOThcdWFjMDRcdWIyZTQuPFwvcD5cclxuPHA+PGltZyB3aWR0aD1cIjI3MlwiIGhlaWdodD1cIjExMlwiIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA2XC9waWMzLlBOR1wiIFwvPjxcL3A+XHJcbjxwPlx1YWRmOFx1YjliYyAzXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM1NDRcdWNlNjhcdWM1ZDAgXHVjNWVjXHViN2VjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM4MWNcdWFjMDFcdWFlMzAgXHViMmU0XHViOTc4IFx1YmMyOVx1ZDVhNVx1YzVkMFx1YzExYyBcdWI0ZTRcdWM1YjRcdWM2NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViYzFmXHVhY2UwIFx1YzljMFx1YjA5OFx1YWMwNFx1YjJlNC4gXHViYjNjXHViODYwIFx1YzVlY1x1YjdlYyBcdWJhODVcdWM3NzQgXHVkNTVjIFx1YWNmM1x1Yzc0NCBcdWJjMWZcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjJhNlx1YzdhMFx1Yzc0NCBcdWM3OTQgXHVjODcwXHVhZDUwXHViMjk0IFx1YWRmOFx1YjliYyA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWJjMWZcdWFjZTAgXHVjOWMwXHViMDk4XHVhYzA0IFx1Y2Q1Y1x1Yzg4NSBcdWMwYzFcdWQwZGNcdWI5Y2MgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPGJyIFwvPlxyXG4mbmJzcDsgXHVhZGY4XHViOWJjIDRcdWI5N2MgXHViY2Y0XHViYTc0LCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHViYTg3IFx1YmE4NSBcdWI0ZTRcdWM1YjQgXHVjNjQwXHVjMTFjIFx1YzViNFx1YjI5MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNWI0XHViMjkwIFx1YWMwNFx1YWNhOVx1YzczY1x1Yjg1YyBcdWIyMDggXHVjNzA0XHVjNWQwIFx1YmMxY1x1Yzc5MFx1YWQ2ZFx1Yzc0NCBcdWIwYjRcdWFjZTAgXHVhYzE0XHViMjk0XHVjOWMwIFx1YWRmOCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjN2FjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjJlOCwgXHVjMTM4IFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMjA4IFx1YzcwNFx1YzVkMCBcdWJjMWNcdWM3OTBcdWFkNmRcdWM3NDQgXHViMGI4IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWI5Y2MgXHVjMGRkXHVhYzAxXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHViMmU0XHViYTc0LCBcdWFkZjhcdWI5YmMgNFx1Yzc1OCBcdWMwYzFcdWQ2NjlcdWM3NzRcdWI3N2NcdWJhNzQgXHVhZGY4XHViOWJjIDNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzEzOCBcdWFjMWNcdWM3NTggXHVkNTU5XHVjMGRkIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHViOWQwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWJiM2NcdWI4NjAgXHViMmU0XHViOTc4IFx1YWMwMFx1YzlkM1x1YzIxOFx1YjNjNCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4pPFwvcD5cclxuPHA+XHVkNTVjXHVkM2I4LCBcdWNjYWJcdWM5ZjggXHVjZTc4XHVjNWQwXHVjMTFjIFx1YzIxOFx1YzljMVx1YzczY1x1Yjg1YyBcdWIwYjRcdWI4MjRcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViMjk0IFx1YmNmNFx1ZDNlZFx1Yzc3NCA0XHVjNzc4IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWM3N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzljMFx1YjljYywgXHVjNzc0IFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWNkMWQgXHViYzFjXHVjNzkwXHVhZDZkXHVjNzc0IFx1YjQ1MCBcdWFjMWNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWNlMFx1YjgyNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NThcdWM5ZjggXHVjOTA0IFx1YzE0Ylx1YzlmOCBcdWNlNzgoMiwgMyksIFx1YzE0Ylx1YzlmOCBcdWM5MDQgXHViMTM3XHVjOWY4IFx1Y2U3OCgzLCA0KSwgXHVjNWVjXHVjMTJmXHVjOWY4IFx1YzkwNCBcdWM3N2NcdWFjZjFcdWM5ZjgoNiwgNykgXHVjZTc4XHVjNzQ0IFx1YzljMFx1YjA5OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNzdjXHVjOWMxXHVjMTIwXHVjNzc0XHVhY2UwIFx1YzEzOCBcdWFjMWNcdWM3NTggXHViYzFjXHVjNzkwXHVhZDZkXHVjNzQ0IFx1YjBhOFx1YWNiY1x1YzljMFx1YjljYywgXHVhYzA0XHVhY2E5XHVjNzc0IFx1Yzc3Y1x1YzgxNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDU1YyBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYzFmXHVhY2UwIFx1YWMwNCBcdWFjYmRcdWI4NWNcdWI4NWMgXHVjNzc4XHVjODE1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG48cD5cdWM1YjRcdWI1YTQgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmMxZlx1YWNlMCBcdWFjMDQgXHVhY2JkXHViODVjXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWMwYzFcdWM1ZDAgXHViMmU0XHViOTc4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWJjMWZcdWFjZTAgXHVhYzA0IFx1YWNmM1x1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM3MDQgXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjICgyLCAxKSwgKDIsIDMpLCAoMiwgNSksICgyLCA3KVx1Yzc0MCBcdWQ1NWMgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmMxZlx1YWNlMCBcdWFjMDQgXHVhY2JkXHViODVjXHVjNzc4XHViMzcwLCBcdWM3NzQgXHVjMTIwIFx1YzU0OFx1YzVkMFx1YjI5NCAoMiwgNilcdWNjOThcdWI3ZmMgXHViMmU0XHViOTc4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWJjMWZcdWFjZTAgXHVhYzA0IFx1YWNmM1x1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzBhY1x1YzJlNFx1Yzc0MCwgXHViYzFjXHVjNzkwXHVhZDZkXHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYyBcdWM3NzRcdWJjODhcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YjBhOFx1YWUzNFx1YWM4YyBcdWM1NDRcdWIyY2MgXHVjNzc0IFx1YzgwNFx1YzVkMCBcdWIyMDhcdWM3NzQgXHVjNjU0XHVjNzQ0IFx1YjU0YyBcdWIwYThcdWM3NDAgXHViYzFjXHVjNzkwXHVhZDZkXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQ8XC9wPlxyXG48cD5cdWMxMzhcdWMwYzFcdWM1ZDBcdWMxMWMgXHVjODFjXHVjNzdjIFx1Y2MyOVx1ZDU1YyBcdWIyZTRcdWMxOWNcdWM3NzRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWJjMWNcdWM3OTBcdWFkNmRcdWM3NDQgXHViMGE4XHVhZTMwXHVhY2UwIFx1YzljMFx1YjA5OFx1YWMwMFx1YWUzMFx1YzVkMCBcdWM3NzRcdWI5N2MgXHVjYzNlXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjliYyA0XHVjNzU4IFx1YWNiZFx1YzZiMCwgXHVjODE1XHViMmY1XHVjNzQwIDdcdWM3NzRcdWIyZTQuIFx1YzVlY1x1YzEyZlx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHVhYzAwXHViODVjXHViODVjIFx1Yzc3Y1x1YWNmMSBcdWJjMWNcdWM3OTBcdWFkNmRcdWM3NDQgXHViYWE4XHViNDUwIFx1YmMxZlx1YWNlMCBcdWM5YzBcdWIwOThcdWFjMDQgXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YjJlNFx1YzE5Y1x1Yzc3NFx1Yjg1YyBcdWNkOTRcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHViNzdjXHVjMmE0XHVjNzU4IFx1YzEzOFx1Yjg1YywgXHVhYzAwXHViODVjIFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IFJcdWFjZmMgQygxJmxlO1IsIEMmbGU7NTAwMClcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHViYzFjXHVjNzkwXHVhZDZkIFx1YzIxOCBOKDMmbGU7TiZsZTs1MDAwKVx1Yzc3NCBcdWM3ODhcdWIyZTQuJm5ic3A7IFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGMgTiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzFjXHVjNzkwXHVhZDZkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YjRhNFx1YjUzMFx1Yjk3OFx1YjJlNC4gXHVjYzk4XHVjNzRjIFx1YWM4M1x1Yzc3NCBcdWM5MDQoXHVjMTM4XHViODVjKSBcdWM4OGNcdWQ0NWNcdWM3NzRcdWFjZTAgXHViMDk4XHVjOTExIFx1YWM4M1x1Yzc3NCBcdWNlNzgoXHVhYzAwXHViODVjKSBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuICgxJmxlO1x1YzkwNCBcdWM4OGNcdWQ0NWMmbGU7UiwgMSZsZTtcdWNlNzggXHVjODhjXHVkNDVjJmxlO0MpIFx1YjQ1MCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhY2Y1XHViYzMxIFx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjXHViMmU0LiBcdWM1ZWNcdWI3ZWMgXHVkNTU5XHVjMGRkXHVjNWQwXHVhYzhjIFx1YmMxZlx1ZDYxNFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWIwOThcdWM2MjhcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWIyZTRcdWMxOWNcdWM3NzRcdWI4NWMgXHVjZDk0XHVjODE1XHViNDE4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHViYzFjXHVjNzkwXHVhZDZkXHVjNzQ0IFx1YjBhOFx1YWUzMFx1YWNlMCBcdWFjMDQgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YmMxY1x1Yzc5MFx1YWQ2ZCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWQ1NThcdWIwOThcdWIzYzQgXHViYzFjXHVhY2FjXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjJlNFx1YmE3NCBcdWFkZjhcdWIwZTUgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzUyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFRyb3VibGVzb21lIEZyb2ciLCJkZXNjcmlwdGlvbiI6IjxwPkluIEtvcmVhLCB0aGUgbmF1Z2h0aW5lc3Mgb2YgdGhlIGNoZW9uZ2dhZWd1cmksIGEgc21hbGwgZnJvZywgaXMgbGVnZW5kYXJ5LiAmbmJzcDtUaGlzIGlzIGEgd2VsbC1kZXNlcnZlZCByZXB1dGF0aW9uLCBiZWNhdXNlIHRoZSBmcm9ncyBqdW1wIHRocm91Z2ggeW91ciByaWNlIHBhZGR5IGF0IG5pZ2h0LCBmbGF0dGVuaW5nIHJpY2UgcGxhbnRzLiAmbmJzcDtJbiB0aGUgbW9ybmluZywgYWZ0ZXIgbm90aW5nIHdoaWNoIHBsYW50cyBoYXZlIGJlZW4gZmxhdHRlbmVkLCB5b3Ugd2FudCB0byBpZGVudGlmeSB0aGUgcGF0aCBvZiB0aGUgZnJvZyB3aGljaCBkaWQgdGhlIG1vc3QgZGFtYWdlLiAmbmJzcDtBIGZyb2cgYWx3YXlzIGp1bXBzIHRocm91Z2ggdGhlIHBhZGR5IGluIGEgc3RyYWlnaHQgbGluZSwgd2l0aCBldmVyeSBob3AgdGhlIHNhbWUgbGVuZ3RoOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2YxKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjUxcHg7IHdpZHRoOjczMXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZjIoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NTlweDsgd2lkdGg6MzYwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RGlmZmVyZW50IGZyb2dzIGNhbiBqdW1wIHdpdGggZGlmZmVyZW50IGhvcCBsZW5ndGhzPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZjMoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjIzcHg7IHdpZHRoOjM4OXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFuZCBpbiBkaWZmZXJlbnQgZGlyZWN0aW9uczxcL3A+XHJcblxyXG48cD5Zb3VyIHJpY2UgcGFkZHkgaGFzIHBsYW50cyBhcnJhbmdlZCBvbiB0aGUgaW50ZXJzZWN0aW9uIHBvaW50cyBvZiBhIGdyaWQgYXMgc2hvd24gaW4gRmlndXJlLTEsIGFuZCB0aGUgdHJvdWJsZXNvbWUgZnJvZ3MgaG9wIGNvbXBsZXRlbHkgdGhyb3VnaCB5b3VyIHBhZGR5LCBzdGFydGluZyBvdXRzaWRlIHRoZSBwYWRkeSBvbiBvbmUgc2lkZSBhbmQgZW5kaW5nIG91dHNpZGUgdGhlIHBhZGR5IG9uIHRoZSBvdGhlciBzaWRlIGFzIHNob3duIGluIEZpZ3VyZS0yOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Y0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMwMHB4OyB3aWR0aDo4NjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5NYW55IGZyb2dzIGNhbiBqdW1wIHRocm91Z2ggdGhlIHBhZGR5LCBob3BwaW5nIGZyb20gcmljZSBwbGFudCB0byByaWNlIHBsYW50LiAmbmJzcDtFdmVyeSBob3AgbGFuZHMgb24gYSBwbGFudCBhbmQgZmxhdHRlbnMgaXQsIGFzIGluIEZpZ3VyZS0zLiAmbmJzcDtOb3RlIHRoYXQgc29tZSBwbGFudHMgbWF5IGJlIGxhbmRlZCBvbiBieSBtb3JlIHRoYW4gb25lIGZyb2cgZHVyaW5nIHRoZSBuaWdodC4gJm5ic3A7T2YgY291cnNlLCB5b3UgY2FuIG5vdCBzZWUgdGhlIGxpbmVzIHNob3dpbmcgdGhlIHBhdGhzIG9mIHRoZSBmcm9ncyBvciBhbnkgb2YgdGhlaXIgaG9wcyBvdXRzaWRlIG9mIHlvdXIgcGFkZHkgJm5kYXNoOyBmb3IgdGhlIHNpdHVhdGlvbiBpbiBGaWd1cmUtMywgd2hhdCB5b3UgY2FuIHNlZSBpcyBzaG93biBpbiBGaWd1cmUtNDo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mNS5wbmdcIiBzdHlsZT1cImhlaWdodDozMDBweDsgd2lkdGg6ODA4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RnJvbSBGaWd1cmUtNCwgeW91IGNhbiByZWNvbnN0cnVjdCBhbGwgdGhlIHBvc3NpYmxlIHBhdGhzIHdoaWNoIHRoZSBmcm9ncyBtYXkgaGF2ZSBmb2xsb3dlZCBhY3Jvc3MgeW91ciBwYWRkeS4gJm5ic3A7WW91IGFyZSBvbmx5IGludGVyZXN0ZWQgaW4gZnJvZ3Mgd2hpY2ggaGF2ZSBsYW5kZWQgb24gYXQgbGVhc3QgMyBvZiB5b3VyIHJpY2UgcGxhbnRzIGluIHRoZWlyIHZveWFnZSB0aHJvdWdoIHRoZSBwYWRkeS4gJm5ic3A7U3VjaCBhIHBhdGggaXMgc2FpZCB0byBiZSBhIGZyb2cgcGF0aC4gJm5ic3A7SW4gdGhpcyBjYXNlLCB0aGF0IG1lYW5zIHRoYXQgdGhlIHRocmVlIHBhdGhzIHNob3duIGluIEZpZ3VyZS0zIGFyZSBmcm9nIHBhdGhzICh0aGVyZSBhcmUgYWxzbyBvdGhlciBwb3NzaWJsZSBmcm9nIHBhdGhzKS4gVGhlIHZlcnRpY2FsIHBhdGggZG93biBjb2x1bW4gMSBtaWdodCBoYXZlIGJlZW4gYSBmcm9nIHBhdGggd2l0aCBob3AgbGVuZ3RoIDQgZXhjZXB0IHRoZXJlIGFyZSBvbmx5IDIgcGxhbnRzIGZsYXR0ZW5lZCBzbyB3ZSBhcmUgbm90IGludGVyZXN0ZWQ7IGFuZCB0aGUgZGlhZ29uYWwgcGF0aCBpbmNsdWRpbmcgdGhlIHBsYW50cyBvbiByb3cgMiBjb2wuIDMsIHJvdyAzIGNvbC4gNCwgYW5kIHJvdyA2IGNvbC4gNyBoYXMgdGhyZWUgZmxhdCBwbGFudHMgYnV0IHRoZXJlIGlzIG5vIHJlZ3VsYXIgaG9wIGxlbmd0aCB3aGljaCBjb3VsZCBoYXZlIHNwYWNlZCB0aGUgaG9wcyBpbiB0aGlzIHdheSB3aGlsZSBzdGlsbCBsYW5kaW5nIG9uIGF0IGxlYXN0IDMgcGxhbnRzLCBhbmQgaGVuY2UgaXQgaXMgbm90IGEgZnJvZyBwYXRoLiAmbmJzcDtOb3RlIGFsc28gdGhhdCBhbG9uZyB0aGUgbGluZSBhIGZyb2cgcGF0aCBmb2xsb3dzIHRoZXJlIG1heSBiZSBhZGRpdGlvbmFsIGZsYXR0ZW5lZCBwbGFudHMgd2hpY2ggZG8gbm90IG5lZWQgdG8gYmUgbGFuZGVkIG9uIGJ5IHRoYXQgcGF0aCAoc2VlIHRoZSBwbGFudCBhdCAoMiwgNikgb24gdGhlIGhvcml6b250YWwgcGF0aCBhY3Jvc3Mgcm93IDIgaW4gRmlndXJlLTQpLCBhbmQgaW4gZmFjdCBzb21lIGZsYXR0ZW5lZCBwbGFudHMgbWF5IG5vdCBiZSBleHBsYWluZWQgYnkgYW55IGZyb2cgcGF0aCBhdCBhbGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIG51bWJlciBvZiBsYW5kaW5ncyBpbiBhbnkgc2luZ2xlIGZyb2cgcGF0aCAod2hlcmUgdGhlIG1heGltdW0gaXMgdGFrZW4gb3ZlciBhbGwgcG9zc2libGUgZnJvZyBwYXRocykuICZuYnNwO0luIEZpZ3VyZS00IHRoZSBhbnN3ZXIgaXMgNywgb2J0YWluZWQgZnJvbSB0aGUgZnJvZyBwYXRoIGFjcm9zcyByb3cgNi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQywgcmVzcGVjdGl2ZWx5IHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucyBpbiB5b3VyIHJpY2UgcGFkZHksIDEgJmxlOyBSLEMgJmxlOyA1MDAwLiAmbmJzcDtUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIHNpbmdsZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgZmxhdHRlbmVkIHJpY2UgcGxhbnRzLCAzICZsZTsgTiAmbGU7IDUwMDAuICZuYnNwO0VhY2ggb2YgdGhlIHJlbWFpbmluZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgdGhlIHJvdyBudW1iZXIgKDEmbGU7IHJvdyBudW1iZXIgJmxlOyBSKSBhbmQgdGhlIGNvbHVtbiBudW1iZXIgKDEmbGU7IGNvbHVtbiBudW1iZXIgJmxlOyBDKSBvZiBhIGZsYXR0ZW5lZCByaWNlIHBsYW50LCBzZXBhcmF0ZWQgYnkgb25lIGJsYW5rLiBFYWNoIGZsYXR0ZW5lZCBwbGFudCBpcyBvbmx5IGxpc3RlZCBvbmNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFRoZSBvdXRwdXQgY29udGFpbnMgb25lIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgbnVtYmVyIG9mIHBsYW50cyBmbGF0dGVuZWQgYWxvbmcgYSBmcm9nIHBhdGggd2hpY2ggZGlkIHRoZSBtb3N0IGRhbWFnZSBpZiB0aGVyZSBleGlzdHMgYXQgbGVhc3Qgb25lIGZyb2cgcGF0aCwgb3RoZXJ3aXNlLCAwLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2002 1번

  • 문제를 번역한 사람: author6