시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhZTAwXHVhY2ZjIFx1YzZkMFx1YWNlMFx1YzljMFx1Yzc1OCBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVkNjA0XHVjMjE4XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVjNzc0IFx1YWUwMFx1Yzc0NCBcdWM2ZDBcdWFjZTBcdWM5YzBcdWM1ZDAgXHVjNGY4IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWI4MDhcdWM3NzRcdWM1NDRcdWM2YzNcdWM3NTggXHVjODFjXHVjNzdjIFx1YWUzNCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVhY2Y1XHViYzMxXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBXXHVjNjQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBXXHViMjk0IFx1YzZkMFx1YWNlMFx1YzljMFx1Yzc1OCBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHVhY2UwLCBOXHVjNzQwIFx1YWUwMFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuICgzICZsZTsgVyAmbGU7IDgwLDAwMCwgMiAmbGU7IE4gJmxlOyA1MCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWUzOFx1Yzc3NCB4PHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIHhpXHViMjk0IGlcdWJjODhcdWM5ZjggXHViMmU4XHVjNWI0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YjJlNC4gKDEgJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IChXLTEpXC8yKTxcL3A+XHJcblxyXG48cD5cdWQ1NmRcdWMwYzEgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViODA4XHVjNzc0XHVjNTQ0XHVjNmMzXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWI4MDhcdWM3NzRcdWM1NDRcdWM2YzNcdWM3NTggXHVjODFjXHVjNzdjIFx1YWUzNCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVhY2Y1XHViYzMxXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzgzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlYXV0aWZ1bCBTcGFjaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UZXh0IGlzIGEgc2VxdWVuY2Ugb2Ygd29yZHMsIGFuZCBhIHdvcmQgY29uc2lzdHMgb2YgY2hhcmFjdGVycy4gWW91ciB0YXNrIGlzIHRvIHB1dCB3b3JkcyBpbnRvIGEgZ3JpZCB3aXRoIFcgY29sdW1ucyBhbmQgc3VcdWZiMDNjaWVudGx5IG1hbnkgbGluZXMuIEZvciB0aGUgYmVhdXR5IG9mIHRoZSBsYXlvdXQsIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucyBoYXZlIHRvIGJlIHNhdGlzIGZpZWQuPFwvcD5cclxuXHJcbjxwPjEuIFRoZSB3b3JkcyBpbiB0aGUgdGV4dCBtdXN0IGJlIHBsYWNlZCBrZWVwaW5nIHRoZWlyIG9yaWdpbmFsIG9yZGVyLiBUaGUgZm9sbG93aW5nIGZpZ3VyZXMgc2hvdyBjb3JyZWN0IGFuZCBpbmNvcnJlY3QgbGF5b3V0IGV4YW1wbGVzIGZvciBhIDQgd29yZCB0ZXh0ICZxdW90O1RoaXMgaXMgYSBwZW4mcXVvdDsgaW50byAxMSBjb2x1bW5zLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDNweDsgd2lkdGg6NTgzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Mi4gQmV0d2VlbiB0d28gd29yZHMgYWRqYWNlbnQgaW4gdGhlIHNhbWUgbGluZSwgeW91IG11c3QgcGxhY2UgYXQgbGVhc3Qgb25lIHNwYWNlIGNoYXJhY3Rlci4gWW91IHNvbWV0aW1lcyBoYXZlIHRvIHB1dCBtb3JlIHRoYW4gb25lIHNwYWNlIGluIG9yZGVyIHRvIG1lZXQgb3RoZXIgY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9sbzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA3cHg7IHdpZHRoOjQxMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjMuIEEgd29yZCBtdXN0IG9jY3VweSB0aGUgc2FtZSBudW1iZXIgb2YgY29uc2VjdXRpdmUgY29sdW1ucyBhcyB0aGUgbnVtYmVyIG9mIGNoYXJhY3RlcnMgaW4gaXQuIFlvdSBjYW5ub3QgYnJlYWsgYSBzaW5nbGUgd29yZCBpbnRvIHR3byBvciBtb3JlIGJ5IGJyZWFraW5nIGl0IGludG8gbGluZXMgb3IgYnkgaW5zZXJ0aW5nIHNwYWNlcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9sbzMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTZweDsgd2lkdGg6NTc1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+NC4gVGhlIHRleHQgbXVzdCBiZSBqdXN0aSBlZCB0byB0aGUgYm90aCBzaWRlcy4gVGhhdCBpcywgdGhlIGZpIHJzdCB3b3JkIG9mIGEgbGluZSBtdXN0IHN0YXJ0IGZyb20gdGhlIGZpIHJzdCBjb2x1bW4gb2YgdGhlIGxpbmUsIGFuZCBleGNlcHQgdGhlIGxhc3QgbGluZSwgdGhlIGxhc3Qgd29yZCBvZiBhIGxpbmUgbXVzdCBlbmQgYXQgdGhlIGxhc3QgY29sdW1uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xvNC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTBweDsgd2lkdGg6NTkwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIHRleHQgaXMgdGhlIG1vc3QgYmVhdXRpZnVsbHkgbGFpZCBvdXQgd2hlbiB0aGVyZSBpcyBubyB1bm5lY2Vzc2FyaWx5IGxvbmcgc3BhY2VzLiBGb3IgaW5zdGFuY2UsIHRoZSBsYXlvdXQgaW4gRmlndXJlIEkuNiBoYXMgYXQgbW9zdCAyIGNvbnRpZ3VvdXMgc3BhY2VzLCB3aGljaCBpcyBtb3JlIGJlYXV0aWZ1bCB0aGFuIHRoYXQgaW4gRmlndXJlIEkuMSwgaGF2aW5nIDMgY29udGlndW91cyBzcGFjZXMuIEdpdmVuIGFuIGlucHV0IHRleHQgYW5kIHRoZSBudW1iZXIgb2YgY29sdW1ucywgcGxlYXNlIGZpIG5kIGEgbGF5b3V0IHN1Y2ggdGhhdCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IGNvbnRpZ3VvdXMgc3BhY2VzIGJldHdlZW4gd29yZHMgaXMgbWluaW11bS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9sbzUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA3cHg7IHdpZHRoOjM2MnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgZGF0YXNldHMsIGVhY2ggaW4gdGhlIGZvbGxvd2luZyBmb3JtYXQuPFwvcD5cclxuXHJcbjxwPlcsIE4sIGFuZCB4aSBhcmUgYWxsIGludGVnZXJzLiBXIGlzIHRoZSBudW1iZXIgb2YgY29sdW1ucyAoMyAmbGU7IFcgJmxlOyA4MCwgMDAwKS4gTiBpcyB0aGUgbnVtYmVyIG9mIHdvcmRzICgyICZsZTsgTiAmbGU7IDUwLCAwMDApLiB4aSBpcyB0aGUgbnVtYmVyIG9mIGNoYXJhY3RlcnMgaW4gdGhlIGktdGggd29yZCAoMSAmbGU7IHhpICZsZTsgKFcgLSAxKVwvMikuIE5vdGUgdGhhdCB0aGUgdXBwZXIgYm91bmQgb24geGkgYXNzdXJlcyB0aGF0IHRoZXJlIGFsd2F5cyBleGlzdHMgYSBsYXlvdXQgc2F0aXNmeWluZyB0aGUgY29uZGl0aW9uczxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBkYXRhc2V0IGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBwcmludCB0aGUgc21hbGxlc3QgcG9zc2libGUgbnVtYmVyIG9mIHRoZSBsb25nZXN0IGNvbnRpZ3VvdXMgc3BhY2VzIGJldHdlZW4gd29yZHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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