시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 92 23 17 32.075%

문제

글은 단어로 이루어져 있고, 단어는 글자로 이루어져 있다. 현수는 단어를 총 W열의 원고지에 써넣으려고 한다. (원고지의 행의 개수는 무한하다) 현수의 좌우명은 "보기 좋은 떡이 먹기도 좋다"이다. 따라서, 원고지에 글을 쓸 때, 항상 아래와 같은 규칙을 지킨다.

1. 글에 포함되어 있는 단어의 순서를 뒤섞으면 안된다. 아래 그림 중 왼쪽 그림은 "This is a pen"을 11열 원고지에 작성할 때 올바른 예이고, 오른쪽 그림은 올바르지 않은 예이다. (단어의 순서를 섞었다)

2. 같은 줄에 있는 두 단어 사이에는 공백이 적어도 한 칸 있어야 한다. 아래 그림은 단어와 단어 사이에 공백을 넣지 않았기 때문에, 올바르지 않은 예이다.

3. 단어는 그 글자수만큼 연속된 칸을 차지해야 한다. 한 단어를 두 줄에 나누어서 쓸 수 없고, 단어 내에 공백이 들어 있으면 안된다. 아래 예는 단어에 포함되어 있는 글자가 연속되지 않아서 현수의 규칙을 지키지 않는 예이다.

4. 글은 양 변에 대해서 균등 정렬이 되어야 한다. 즉, 각 줄의 첫 번째 단어는 첫 번째 열에서 시작해어야 하고, 마지막 줄을 제외한 모든 줄의 마지막 단어는 마지막 열에서 끝나야 한다. 아래 그림은 양 변에 대해서 균등하지 않은 예이다.

글은 불필요한 긴 공백이 없을 때 아름다운 레이아웃이라고 한다. 즉, 제일 긴 연속된 공백의 길이가 최소가 되어야 한다. 예를 들어, 아래 그림은 "This is a pen"을 11열 원고지에 쓸 때, 현수의 규칙을 지키면서 가장 아름다운 레이아웃이다. 제일 긴 연속된 공백의 길이가 2이다. 또, 1번 조건의 아래 왼쪽 그림은 3이다.

글과 원고지의 열의 개수가 주어진다. 이때, 현수의 규칙을 지키면서 이 글을 원고지에 쓸 때, 가장 아름다운 레이아웃의 제일 긴 연속된 공백의 길이를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 W와 N이 주어진다. W는 원고지의 열의 개수이고, N은 글에 포함되어 있는 단어의 개수이다. (3 ≤ W ≤ 80,000, 2 ≤ N ≤ 50,000)

둘째 줄에는 단어의 길이 xi가 주어진다. xi는 i번째 단어의 길이이다. (1 ≤ xi ≤ (W-1)/2)

항상 문제의 조건을 만족하는 레이아웃이 존재한다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 가장 아름다운 레이아웃의 제일 긴 연속된 공백의 길이를 출력한다.

예제 입력 1

11 4
4 2 1 3
5 7
1 1 1 2 2 1 2
11 7
3 1 3 1 3 3 4
100 3
30 30 39
30 3
2 5 3
0 0

예제 출력 1

2
1
2
40
1
W3sicHJvYmxlbV9pZCI6IjM4MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViODA4XHVjNzc0XHVjNTQ0XHVjNmMzIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMDBcdWM3NDAgXHViMmU4XHVjNWI0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YjJlOFx1YzViNFx1YjI5NCBcdWFlMDBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVkNjA0XHVjMjE4XHViMjk0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWNkMWQgV1x1YzVmNFx1Yzc1OCBcdWM2ZDBcdWFjZTBcdWM5YzBcdWM1ZDAgXHVjMzY4XHViMTIzXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gKFx1YzZkMFx1YWNlMFx1YzljMFx1Yzc1OCBcdWQ1ODlcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YmIzNFx1ZDU1Y1x1ZDU1OFx1YjJlNCkgXHVkNjA0XHVjMjE4XHVjNzU4IFx1Yzg4Y1x1YzZiMFx1YmE4NVx1Yzc0MCAmcXVvdDtcdWJjZjRcdWFlMzAgXHVjODhiXHVjNzQwIFx1YjVhMVx1Yzc3NCBcdWJhMzlcdWFlMzBcdWIzYzQgXHVjODhiXHViMmU0JnF1b3Q7XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzZkMFx1YWNlMFx1YzljMFx1YzVkMCBcdWFlMDBcdWM3NDQgXHVjNGY4IFx1YjU0YywgXHVkNTZkXHVjMGMxIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MS4gXHVhZTAwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI0YTRcdWMxMWVcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIFx1YzkxMSBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwICZxdW90O1RoaXMgaXMgYSBwZW4mcXVvdDtcdWM3NDQgMTFcdWM1ZjQgXHVjNmQwXHVhY2UwXHVjOWMwXHVjNWQwIFx1Yzc5MVx1YzEzMVx1ZDU2MCBcdWI1NGMgXHVjNjJjXHViYzE0XHViOTc4IFx1YzYwOFx1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM2MmNcdWJjMTRcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzYwOFx1Yzc3NFx1YjJlNC4gKFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjMTFlXHVjNWM4XHViMmU0KTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JzMSgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDo3MHB4OyB3aWR0aDo1NzRweFwiIFwvPjxcL3A+XHJcblxyXG48cD4yLiBcdWFjMTlcdWM3NDAgXHVjOTA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHViMmU4XHVjNWI0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWNlNzggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWIyZThcdWM1YjRcdWM2NDAgXHViMmU4XHVjNWI0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViMTIzXHVjOWMwIFx1YzU0YVx1YzU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzYyY1x1YmMxNFx1Yjk3NFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JzMigxKS5wbmdcIiBzdHlsZT1cImhlaWdodDo2OHB4OyB3aWR0aDoyOTJweFwiIFwvPjxcL3A+XHJcblxyXG48cD4zLiBcdWIyZThcdWM1YjRcdWIyOTQgXHVhZGY4IFx1YWUwMFx1Yzc5MFx1YzIxOFx1YjljY1x1ZDA3YyBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjZTc4XHVjNzQ0IFx1Y2MyOFx1YzljMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWIyZThcdWM1YjRcdWI5N2MgXHViNDUwIFx1YzkwNFx1YzVkMCBcdWIwOThcdWIyMDRcdWM1YjRcdWMxMWMgXHVjNGY4IFx1YzIxOCBcdWM1YzZcdWFjZTAsIFx1YjJlOFx1YzViNCBcdWIwYjRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzc0IFx1YjRlNFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVjNjA4XHViMjk0IFx1YjJlOFx1YzViNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM1ZjBcdWMxOGRcdWI0MThcdWM5YzAgXHVjNTRhXHVjNTQ0XHVjMTFjIFx1ZDYwNFx1YzIxOFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnMzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojc1cHg7IHdpZHRoOjU3NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjQuIFx1YWUwMFx1Yzc0MCBcdWM1OTEgXHViY2MwXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFkZTBcdWI0ZjEgXHVjODE1XHViODJjXHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjJlOFx1YzViNFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjOTA0XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWIyZThcdWM1YjRcdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOThcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzU5MSBcdWJjYzBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YWRlMFx1YjRmMVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JzNC5wbmdcIiBzdHlsZT1cImhlaWdodDo3OXB4OyB3aWR0aDo1ODRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFlMDBcdWM3NDAgXHViZDg4XHVkNTQ0XHVjNjk0XHVkNTVjIFx1YWUzNCBcdWFjZjVcdWJjMzFcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0YyBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViODA4XHVjNzc0XHVjNTQ0XHVjNmMzXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWM4MWNcdWM3N2MgXHVhZTM0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWFjZjVcdWJjMzFcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwICZxdW90O1RoaXMgaXMgYSBwZW4mcXVvdDtcdWM3NDQgMTFcdWM1ZjQgXHVjNmQwXHVhY2UwXHVjOWMwXHVjNWQwIFx1YzRmOCBcdWI1NGMsIFx1ZDYwNFx1YzIxOFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViODA4XHVjNzc0XHVjNTQ0XHVjNmMzXHVjNzc0XHViMmU0LiBcdWM4MWNcdWM3N2MgXHVhZTM0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWFjZjVcdWJjMzFcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDJcdWM3NzRcdWIyZTQuIFx1YjYxMCwgMVx1YmM4OCBcdWM4NzBcdWFjNzRcdWM3NTggXHVjNTQ0XHViNzk4IFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iczUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzFweDsgd2lkdGg6Mjg4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhZTAwXHVhY2ZjIFx1YzZkMFx1YWNlMFx1YzljMFx1Yzc1OCBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQ2MDRcdWMyMThcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWM3NzQgXHVhZTAwXHVjNzQ0IFx1YzZkMFx1YWNlMFx1YzljMFx1YzVkMCBcdWM0ZjggXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YjgwOFx1Yzc3NFx1YzU0NFx1YzZjM1x1Yzc1OCBcdWM4MWNcdWM3N2MgXHVhZTM0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWFjZjVcdWJjMzFcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFdcdWM2NDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFdcdWIyOTQgXHVjNmQwXHVhY2UwXHVjOWMwXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWFjZTAsIE5cdWM3NDAgXHVhZTAwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gKDMgJmxlOyBXICZsZTsgODAsMDAwLCAyICZsZTsgTiAmbGU7IDUwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0IHg8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4geGlcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiAoMSAmbGU7IHg8c3ViPmk8XC9zdWI+ICZsZTsgKFctMSlcLzIpPFwvcD5cclxuXHJcbjxwPlx1ZDU2ZFx1YzBjMSBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI4MDhcdWM3NzRcdWM1NDRcdWM2YzNcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMmbmJzcDtcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YjgwOFx1Yzc3NFx1YzU0NFx1YzZjM1x1Yzc1OCBcdWM4MWNcdWM3N2MgXHVhZTM0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWFjZjVcdWJjMzFcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzODMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmVhdXRpZnVsIFNwYWNpbmciLCJkZXNjcmlwdGlvbiI6IjxwPlRleHQgaXMgYSBzZXF1ZW5jZSBvZiB3b3JkcywgYW5kIGEgd29yZCBjb25zaXN0cyBvZiBjaGFyYWN0ZXJzLiBZb3VyIHRhc2sgaXMgdG8gcHV0IHdvcmRzIGludG8gYSBncmlkIHdpdGggVyBjb2x1bW5zIGFuZCBzdVx1ZmIwM2NpZW50bHkgbWFueSBsaW5lcy4gRm9yIHRoZSBiZWF1dHkgb2YgdGhlIGxheW91dCwgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zIGhhdmUgdG8gYmUgc2F0aXMgZmllZC48XC9wPlxyXG5cclxuPHA+MS4gVGhlIHdvcmRzIGluIHRoZSB0ZXh0IG11c3QgYmUgcGxhY2VkIGtlZXBpbmcgdGhlaXIgb3JpZ2luYWwgb3JkZXIuIFRoZSBmb2xsb3dpbmcgZmlndXJlcyBzaG93IGNvcnJlY3QgYW5kIGluY29ycmVjdCBsYXlvdXQgZXhhbXBsZXMgZm9yIGEgNCB3b3JkIHRleHQgJnF1b3Q7VGhpcyBpcyBhIHBlbiZxdW90OyBpbnRvIDExIGNvbHVtbnMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbG8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwM3B4OyB3aWR0aDo1ODNweFwiIFwvPjxcL3A+XHJcblxyXG48cD4yLiBCZXR3ZWVuIHR3byB3b3JkcyBhZGphY2VudCBpbiB0aGUgc2FtZSBsaW5lLCB5b3UgbXVzdCBwbGFjZSBhdCBsZWFzdCBvbmUgc3BhY2UgY2hhcmFjdGVyLiBZb3Ugc29tZXRpbWVzIGhhdmUgdG8gcHV0IG1vcmUgdGhhbiBvbmUgc3BhY2UgaW4gb3JkZXIgdG8gbWVldCBvdGhlciBjb25kaXRpb25zLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xvMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDdweDsgd2lkdGg6NDEwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+My4gQSB3b3JkIG11c3Qgb2NjdXB5IHRoZSBzYW1lIG51bWJlciBvZiBjb25zZWN1dGl2ZSBjb2x1bW5zIGFzIHRoZSBudW1iZXIgb2YgY2hhcmFjdGVycyBpbiBpdC4gWW91IGNhbm5vdCBicmVhayBhIHNpbmdsZSB3b3JkIGludG8gdHdvIG9yIG1vcmUgYnkgYnJlYWtpbmcgaXQgaW50byBsaW5lcyBvciBieSBpbnNlcnRpbmcgc3BhY2VzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xvMy5wbmdcIiBzdHlsZT1cImhlaWdodDo5NnB4OyB3aWR0aDo1NzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD40LiBUaGUgdGV4dCBtdXN0IGJlIGp1c3RpIGVkIHRvIHRoZSBib3RoIHNpZGVzLiBUaGF0IGlzLCB0aGUgZmkgcnN0IHdvcmQgb2YgYSBsaW5lIG11c3Qgc3RhcnQgZnJvbSB0aGUgZmkgcnN0IGNvbHVtbiBvZiB0aGUgbGluZSwgYW5kIGV4Y2VwdCB0aGUgbGFzdCBsaW5lLCB0aGUgbGFzdCB3b3JkIG9mIGEgbGluZSBtdXN0IGVuZCBhdCB0aGUgbGFzdCBjb2x1bW4uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbG80LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExMHB4OyB3aWR0aDo1OTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgdGV4dCBpcyB0aGUgbW9zdCBiZWF1dGlmdWxseSBsYWlkIG91dCB3aGVuIHRoZXJlIGlzIG5vIHVubmVjZXNzYXJpbHkgbG9uZyBzcGFjZXMuIEZvciBpbnN0YW5jZSwgdGhlIGxheW91dCBpbiBGaWd1cmUgSS42IGhhcyBhdCBtb3N0IDIgY29udGlndW91cyBzcGFjZXMsIHdoaWNoIGlzIG1vcmUgYmVhdXRpZnVsIHRoYW4gdGhhdCBpbiBGaWd1cmUgSS4xLCBoYXZpbmcgMyBjb250aWd1b3VzIHNwYWNlcy4gR2l2ZW4gYW4gaW5wdXQgdGV4dCBhbmQgdGhlIG51bWJlciBvZiBjb2x1bW5zLCBwbGVhc2UgZmkgbmQgYSBsYXlvdXQgc3VjaCB0aGF0IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgY29udGlndW91cyBzcGFjZXMgYmV0d2VlbiB3b3JkcyBpcyBtaW5pbXVtLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xvNS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDdweDsgd2lkdGg6MzYycHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSBkYXRhc2V0cywgZWFjaCBpbiB0aGUgZm9sbG93aW5nIGZvcm1hdC48XC9wPlxyXG5cclxuPHA+VywgTiwgYW5kIHhpIGFyZSBhbGwgaW50ZWdlcnMuIFcgaXMgdGhlIG51bWJlciBvZiBjb2x1bW5zICgzICZsZTsgVyAmbGU7IDgwLCAwMDApLiBOIGlzIHRoZSBudW1iZXIgb2Ygd29yZHMgKDIgJmxlOyBOICZsZTsgNTAsIDAwMCkuIHhpIGlzIHRoZSBudW1iZXIgb2YgY2hhcmFjdGVycyBpbiB0aGUgaS10aCB3b3JkICgxICZsZTsgeGkgJmxlOyAoVyAtIDEpXC8yKS4gTm90ZSB0aGF0IHRoZSB1cHBlciBib3VuZCBvbiB4aSBhc3N1cmVzIHRoYXQgdGhlcmUgYWx3YXlzIGV4aXN0cyBhIGxheW91dCBzYXRpc2Z5aW5nIHRoZSBjb25kaXRpb25zPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGRhdGFzZXQgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIHByaW50IHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBudW1iZXIgb2YgdGhlIGxvbmdlc3QgY29udGlndW91cyBzcGFjZXMgYmV0d2VlbiB3b3Jkcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2012 in Tokyo I번

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