시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB96241831.579%

문제

글은 단어로 이루어져 있고, 단어는 글자로 이루어져 있다. 현수는 단어를 총 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+MS4gXHVhZTAwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI0YTRcdWMxMWVcdWM3M2NcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliYyBcdWM5MTEgXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCAmcXVvdDtUaGlzIGlzIGEgcGVuJnF1b3Q7XHVjNzQ0IDExXHVjNWY0IFx1YzZkMFx1YWNlMFx1YzljMFx1YzVkMCBcdWM3OTFcdWMxMzFcdWQ1NjAgXHViNTRjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWM2MDhcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNjJjXHViYzE0XHViOTc0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM2MDhcdWM3NzRcdWIyZTQuIChcdWIyZThcdWM1YjRcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzExZVx1YzVjOFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iczEoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzBweDsgd2lkdGg6NTc0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Mi4gXHVhYzE5XHVjNzQwIFx1YzkwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNDUwIFx1YjJlOFx1YzViNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzc0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVjZTc4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViMmU4XHVjNWI0XHVjNjQwIFx1YjJlOFx1YzViNCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YjEyM1x1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM2MmNcdWJjMTRcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iczIoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjhweDsgd2lkdGg6MjkycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+My4gXHViMmU4XHVjNWI0XHViMjk0IFx1YWRmOCBcdWFlMDBcdWM3OTBcdWMyMThcdWI5Y2NcdWQwN2MgXHVjNWYwXHVjMThkXHViNDFjIFx1Y2U3OFx1Yzc0NCBcdWNjMjhcdWM5YzBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1NWMgXHViMmU4XHVjNWI0XHViOTdjIFx1YjQ1MCBcdWM5MDRcdWM1ZDAgXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjIFx1YzRmOCBcdWMyMTggXHVjNWM2XHVhY2UwLCBcdWIyZThcdWM1YjQgXHViMGI0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWI0ZTRcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWM2MDhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzVmMFx1YzE4ZFx1YjQxOFx1YzljMCBcdWM1NGFcdWM1NDRcdWMxMWMgXHVkNjA0XHVjMjE4XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iczMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzVweDsgd2lkdGg6NTc0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+NC4gXHVhZTAwXHVjNzQwIFx1YzU5MSBcdWJjYzBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YWRlMFx1YjRmMSBcdWM4MTVcdWI4MmNcdWM3NzQgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWFjMDEgXHVjOTA0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViMmU4XHVjNWI0XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM5MDRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YjJlOFx1YzViNFx1YjI5NCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNWY0XHVjNWQwXHVjMTFjIFx1YjA1ZFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNTkxIFx1YmNjMFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVhZGUwXHViNGYxXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnM0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojc5cHg7IHdpZHRoOjU4NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWUwMFx1Yzc0MCBcdWJkODhcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhZTM0IFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWM1YzZcdWM3NDQgXHViNTRjIFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWI4MDhcdWM3NzRcdWM1NDRcdWM2YzNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YzgxY1x1Yzc3YyBcdWFlMzQgXHVjNWYwXHVjMThkXHViNDFjIFx1YWNmNVx1YmMzMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgJnF1b3Q7VGhpcyBpcyBhIHBlbiZxdW90O1x1Yzc0NCAxMVx1YzVmNCBcdWM2ZDBcdWFjZTBcdWM5YzBcdWM1ZDAgXHVjNGY4IFx1YjU0YywgXHVkNjA0XHVjMjE4XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWI4MDhcdWM3NzRcdWM1NDRcdWM2YzNcdWM3NzRcdWIyZTQuIFx1YzgxY1x1Yzc3YyBcdWFlMzQgXHVjNWYwXHVjMThkXHViNDFjIFx1YWNmNVx1YmMzMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgMlx1Yzc3NFx1YjJlNC4gXHViNjEwLCAxXHViYzg4IFx1Yzg3MFx1YWM3NFx1Yzc1OCBcdWM1NDRcdWI3OTggXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCAzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JzNS5wbmdcIiBzdHlsZT1cImhlaWdodDo3MXB4OyB3aWR0aDoyODhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFlMDBcdWFjZmMgXHVjNmQwXHVhY2UwXHVjOWMwXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDYwNFx1YzIxOFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1Yzc3NCBcdWFlMDBcdWM3NDQgXHVjNmQwXHVhY2UwXHVjOWMwXHVjNWQwIFx1YzRmOCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViODA4XHVjNzc0XHVjNTQ0XHVjNmMzXHVjNzU4IFx1YzgxY1x1Yzc3YyBcdWFlMzQgXHVjNWYwXHVjMThkXHViNDFjIFx1YWNmNVx1YmMzMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgV1x1YzY0MCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gV1x1YjI5NCBcdWM2ZDBcdWFjZTBcdWM5YzBcdWM3NTggXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YWNlMCwgTlx1Yzc0MCBcdWFlMDBcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiAoMyAmbGU7IFcgJmxlOyA4MCwwMDAsIDIgJmxlOyBOICZsZTsgNTAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzQgeDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiB4aVx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWIyZTQuICgxICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmxlOyAoVy0xKVwvMik8XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YjgwOFx1Yzc3NFx1YzU0NFx1YzZjM1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViODA4XHVjNzc0XHVjNTQ0XHVjNmMzXHVjNzU4IFx1YzgxY1x1Yzc3YyBcdWFlMzQgXHVjNWYwXHVjMThkXHViNDFjIFx1YWNmNVx1YmMzMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM4MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCZWF1dGlmdWwgU3BhY2luZyIsImRlc2NyaXB0aW9uIjoiPHA+VGV4dCBpcyBhIHNlcXVlbmNlIG9mIHdvcmRzLCBhbmQgYSB3b3JkIGNvbnNpc3RzIG9mIGNoYXJhY3RlcnMuIFlvdXIgdGFzayBpcyB0byBwdXQgd29yZHMgaW50byBhIGdyaWQgd2l0aCBXIGNvbHVtbnMgYW5kIHN1XHVmYjAzY2llbnRseSBtYW55IGxpbmVzLiBGb3IgdGhlIGJlYXV0eSBvZiB0aGUgbGF5b3V0LCB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMgaGF2ZSB0byBiZSBzYXRpcyBmaWVkLjxcL3A+XHJcblxyXG48cD4xLiBUaGUgd29yZHMgaW4gdGhlIHRleHQgbXVzdCBiZSBwbGFjZWQga2VlcGluZyB0aGVpciBvcmlnaW5hbCBvcmRlci4gVGhlIGZvbGxvd2luZyBmaWd1cmVzIHNob3cgY29ycmVjdCBhbmQgaW5jb3JyZWN0IGxheW91dCBleGFtcGxlcyBmb3IgYSA0IHdvcmQgdGV4dCAmcXVvdDtUaGlzIGlzIGEgcGVuJnF1b3Q7IGludG8gMTEgY29sdW1ucy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9sbzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTAzcHg7IHdpZHRoOjU4M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjIuIEJldHdlZW4gdHdvIHdvcmRzIGFkamFjZW50IGluIHRoZSBzYW1lIGxpbmUsIHlvdSBtdXN0IHBsYWNlIGF0IGxlYXN0IG9uZSBzcGFjZSBjaGFyYWN0ZXIuIFlvdSBzb21ldGltZXMgaGF2ZSB0byBwdXQgbW9yZSB0aGFuIG9uZSBzcGFjZSBpbiBvcmRlciB0byBtZWV0IG90aGVyIGNvbmRpdGlvbnMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbG8yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwN3B4OyB3aWR0aDo0MTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD4zLiBBIHdvcmQgbXVzdCBvY2N1cHkgdGhlIHNhbWUgbnVtYmVyIG9mIGNvbnNlY3V0aXZlIGNvbHVtbnMgYXMgdGhlIG51bWJlciBvZiBjaGFyYWN0ZXJzIGluIGl0LiBZb3UgY2Fubm90IGJyZWFrIGEgc2luZ2xlIHdvcmQgaW50byB0d28gb3IgbW9yZSBieSBicmVha2luZyBpdCBpbnRvIGxpbmVzIG9yIGJ5IGluc2VydGluZyBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbG8zLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojk2cHg7IHdpZHRoOjU3NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPjQuIFRoZSB0ZXh0IG11c3QgYmUganVzdGkgZWQgdG8gdGhlIGJvdGggc2lkZXMuIFRoYXQgaXMsIHRoZSBmaSByc3Qgd29yZCBvZiBhIGxpbmUgbXVzdCBzdGFydCBmcm9tIHRoZSBmaSByc3QgY29sdW1uIG9mIHRoZSBsaW5lLCBhbmQgZXhjZXB0IHRoZSBsYXN0IGxpbmUsIHRoZSBsYXN0IHdvcmQgb2YgYSBsaW5lIG11c3QgZW5kIGF0IHRoZSBsYXN0IGNvbHVtbi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9sbzQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTEwcHg7IHdpZHRoOjU5MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSB0ZXh0IGlzIHRoZSBtb3N0IGJlYXV0aWZ1bGx5IGxhaWQgb3V0IHdoZW4gdGhlcmUgaXMgbm8gdW5uZWNlc3NhcmlseSBsb25nIHNwYWNlcy4gRm9yIGluc3RhbmNlLCB0aGUgbGF5b3V0IGluIEZpZ3VyZSBJLjYgaGFzIGF0IG1vc3QgMiBjb250aWd1b3VzIHNwYWNlcywgd2hpY2ggaXMgbW9yZSBiZWF1dGlmdWwgdGhhbiB0aGF0IGluIEZpZ3VyZSBJLjEsIGhhdmluZyAzIGNvbnRpZ3VvdXMgc3BhY2VzLiBHaXZlbiBhbiBpbnB1dCB0ZXh0IGFuZCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMsIHBsZWFzZSBmaSBuZCBhIGxheW91dCBzdWNoIHRoYXQgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBjb250aWd1b3VzIHNwYWNlcyBiZXR3ZWVuIHdvcmRzIGlzIG1pbmltdW0uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbG81LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwN3B4OyB3aWR0aDozNjJweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIGRhdGFzZXRzLCBlYWNoIGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0LjxcL3A+XHJcblxyXG48cD5XLCBOLCBhbmQgeGkgYXJlIGFsbCBpbnRlZ2Vycy4gVyBpcyB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgKDMgJmxlOyBXICZsZTsgODAsIDAwMCkuIE4gaXMgdGhlIG51bWJlciBvZiB3b3JkcyAoMiAmbGU7IE4gJmxlOyA1MCwgMDAwKS4geGkgaXMgdGhlIG51bWJlciBvZiBjaGFyYWN0ZXJzIGluIHRoZSBpLXRoIHdvcmQgKDEgJmxlOyB4aSAmbGU7IChXIC0gMSlcLzIpLiBOb3RlIHRoYXQgdGhlIHVwcGVyIGJvdW5kIG9uIHhpIGFzc3VyZXMgdGhhdCB0aGVyZSBhbHdheXMgZXhpc3RzIGEgbGF5b3V0IHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbnM8XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgZGF0YXNldCBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgcHJpbnQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIG51bWJlciBvZiB0aGUgbG9uZ2VzdCBjb250aWd1b3VzIHNwYWNlcyBiZXR3ZWVuIHdvcmRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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