시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 64 MB 310 66 46 18.623%

문제

지안지아는 타이완에서의 휴가를 계획하고 있다. 휴가동안 지안지아는 도시에서 도시로 이동하고 도시 안의 관광지들을 방문할 것이다.

타이완에는 하나의 고속도로를 따라서 n개의 도시들이 위치한다. 이 도시들은 순서대로 0부터 n-1까지의 번호가 붙어있다. 임의의 i(0 < i < n-1)에 대해서, 도시 i의 인접한 도시는 도시 i-1과 i+1이다. 도시 0과 인접한 도시는 도시 1뿐이고, 도시 n-1과 인접한 도시는 도시 n-2뿐이다.

각 도시에는 여러 관광지들이 있다. 지안지아는 d일 동안의 휴가를 얻었고 가능한 많은 관광지들을 방문하고 싶다. 지안지아는 휴가를 시작할 도시를 선택했다. 휴가기간동안 매일 지안지아는 인접한 도시로 움직이거나 또는 현재 도시의 관광지들을 모두 방문한다. 그러나 두 행동을 하루에 모두 할수는 없다. 지안지아는 한 도시에 여러 번 머물더라도 같은 도시안의 관광지들을 결코 두 번 방문하지는 않는다. 지안지아가 가능한 많은 서로 다른 관광지들을 방문하도록 도와주자.

지안지아는 7일의 휴가를 얻었고, (아래 표와 같이) 5개의 도시가 있고 도시 2에서 휴가를 시작하였다. 첫 번째 날 지안지아는 도시 2의 20개 관광지를 방문한다. 두 번째 날 지안지아는 도시 2에 서 도시 3으로 이동하고 세 번째 날 도시 3의 30개 관광지들을 방문한다. 다음 3일동안 지안지아 는 도시 3에서 도시 0으로 이동해서 일곱 번째 날에 도시 0의 10개 관광지들을 방문한다. 따라서 지안지아가 방문한 관광지의 총 개수는 20 + 30 + 10 = 60이고 이것은 그가 도시 2에서 시작해서 7일 동안 방문할 수 있는 관광지들의 최대 개수이다.

도시 관광지 개수
0 10
1 2
2 20
3 30
4 1
행동
1 도시 2의 관광지들을 방문
2 도시 2에서 도시 3으로 이동
3 도시 3의 관광지들을 방문
4 도시 3에서 도시 2로 이동
5 도시 2에서 도시 1로 이동
6 도시 1에서 도시 0으로 이동
7 도시 0의 관광지들을 방문

지안지아가 방문할 수 있는 관광지들의 최대 개수를 계산하시오.

입력

첫째 줄에 도시의 개수 n, 시작 도시의 번호 start, 휴가일의 수 d가 주어진다. (2 ≤ n ≤ 100,000)

둘째 줄에는 도시 i의 관광지 개수가 0번 도시부터 순서대로 공백으로 구분해 주어진다. 한 도시 안의 관광지들의 최대 개수는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 또, 0 ≤ d ≤ 2n + ⌊n/2⌋를 만족한다.

출력

지안지아가 방문할 수 있는 관광지의 최대 개수를 출력한다.

예제 입력 1

5 2 7
10 2 20 30 1

예제 출력 1

60
W3sicHJvYmxlbV9pZCI6IjEwMDc2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNzM0XHVhYzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgXHVkMGMwXHVjNzc0XHVjNjQ0XHVjNWQwXHVjMTFjXHVjNzU4IFx1ZDczNFx1YWMwMFx1Yjk3YyBcdWFjYzRcdWQ2OGRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ3MzRcdWFjMDBcdWIzZDlcdWM1NDggXHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHViMjk0IFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWIzYzRcdWMyZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhY2UwIFx1YjNjNFx1YzJkYyBcdWM1NDhcdWM3NTggXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDBjMFx1Yzc3NFx1YzY0NFx1YzVkMFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViOTdjIFx1YjUzMFx1Yjc3Y1x1YzExYyBuXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc3NCBcdWM3MDRcdWNlNThcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWIzYzRcdWMyZGNcdWI0ZTRcdWM3NDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIDBcdWJkODBcdWQxMzAgbi0xXHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBpKDAgJmx0OyBpICZsdDsgbi0xKVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjNjNFx1YzJkYyBpXHVjNzU4IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWIzYzRcdWMyZGNcdWIyOTQgXHViM2M0XHVjMmRjIGktMVx1YWNmYyBpKzFcdWM3NzRcdWIyZTQuIFx1YjNjNFx1YzJkYyAwXHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWIzYzRcdWMyZGNcdWIyOTQgXHViM2M0XHVjMmRjIDFcdWJmZDBcdWM3NzRcdWFjZTAsIFx1YjNjNFx1YzJkYyBuLTFcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjNjNFx1YzJkY1x1YjI5NCBcdWIzYzRcdWMyZGMgbi0yXHViZmQwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHViM2M0XHVjMmRjXHVjNWQwXHViMjk0IFx1YzVlY1x1YjdlYyBcdWFkMDBcdWFkMTFcdWM5YzBcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgZFx1Yzc3YyBcdWIzZDlcdWM1NDhcdWM3NTggXHVkNzM0XHVhYzAwXHViOTdjIFx1YzViYlx1YzVjOFx1YWNlMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgXHVkNzM0XHVhYzAwXHViOTdjIFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTg4XHViMmU0LiBcdWQ3MzRcdWFjMDBcdWFlMzBcdWFjMDRcdWIzZDlcdWM1NDggXHViOWU0XHVjNzdjIFx1YzljMFx1YzU0OFx1YzljMFx1YzU0NFx1YjI5NCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViM2M0XHVjMmRjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YWM3MFx1YjA5OCBcdWI2MTBcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWFkMDBcdWFkMTFcdWM5YzBcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YmMyOVx1YmIzOFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YjQ1MCBcdWQ1ODlcdWIzZDlcdWM3NDQgXHVkNTU4XHViOGU4XHVjNWQwIFx1YmFhOFx1YjQ1MCBcdWQ1NjBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgXHVkNTVjIFx1YjNjNFx1YzJkY1x1YzVkMCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YmEzOFx1YmIzY1x1YjM1NFx1Yjc3Y1x1YjNjNCBcdWFjMTlcdWM3NDAgXHViM2M0XHVjMmRjXHVjNTQ4XHVjNzU4IFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc0NCBcdWFjYjBcdWNmNTQgXHViNDUwIFx1YmM4OCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzBcdWIyOTQgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjljZVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIzYzRcdWI4NWQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgN1x1Yzc3Y1x1Yzc1OCBcdWQ3MzRcdWFjMDBcdWI5N2MgXHVjNWJiXHVjNWM4XHVhY2UwLCAoXHVjNTQ0XHViNzk4IFx1ZDQ1Y1x1YzY0MCBcdWFjMTlcdWM3NzQpIDVcdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHVhYzAwIFx1Yzc4OFx1YWNlMCBcdWIzYzRcdWMyZGMgMlx1YzVkMFx1YzExYyBcdWQ3MzRcdWFjMDBcdWI5N2MgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNjAwXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjBhMCBcdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWIyOTQgXHViM2M0XHVjMmRjIDJcdWM3NTggMjBcdWFjMWMgXHVhZDAwXHVhZDExXHVjOWMwXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWIwYTAgXHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHViMjk0IFx1YjNjNFx1YzJkYyAyXHVjNWQwIFx1YzExYyBcdWIzYzRcdWMyZGMgM1x1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjZTAgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWIwYTAgXHViM2M0XHVjMmRjIDNcdWM3NTggMzBcdWFjMWMgXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVjNzRjIDNcdWM3N2NcdWIzZDlcdWM1NDggXHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0IFx1YjI5NCBcdWIzYzRcdWMyZGMgM1x1YzVkMFx1YzExYyBcdWIzYzRcdWMyZGMgMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NzRcdWMxMWMgXHVjNzdjXHVhY2YxIFx1YmM4OFx1YzlmOCBcdWIwYTBcdWM1ZDAgXHViM2M0XHVjMmRjIDBcdWM3NTggMTBcdWFjMWMgXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzljMFx1YzU0OFx1YzljMFx1YzU0NFx1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVhZDAwXHVhZDExXHVjOWMwXHVjNzU4IFx1Y2QxZCBcdWFjMWNcdWMyMThcdWIyOTQgMjAgKyAzMCArIDEwID0gNjBcdWM3NzRcdWFjZTAgXHVjNzc0XHVhYzgzXHVjNzQwIFx1YWRmOFx1YWMwMCBcdWIzYzRcdWMyZGMgMlx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgN1x1Yzc3YyBcdWIzZDlcdWM1NDggXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoyMCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdWIzYzRcdWMyZGM8XC90aD5cclxuXHRcdFx0PHRoPlx1YWQwMFx1YWQxMVx1YzljMCBcdWFjMWNcdWMyMTg8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHQ8XC90Ym9keT5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjIwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjMwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDozMCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdWM3N2M8XC90aD5cclxuXHRcdFx0PHRoPlx1ZDU4OVx1YjNkOTxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdDxcL3Rib2R5PlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPlx1YjNjNFx1YzJkYyAyXHVjNzU4IFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc0NCBcdWJjMjlcdWJiMzg8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViM2M0XHVjMmRjIDJcdWM1ZDBcdWMxMWMgXHViM2M0XHVjMmRjIDNcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPlx1YjNjNFx1YzJkYyAzXHVjNzU4IFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc0NCBcdWJjMjlcdWJiMzg8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViM2M0XHVjMmRjIDNcdWM1ZDBcdWMxMWMgXHViM2M0XHVjMmRjIDJcdWI4NWMgXHVjNzc0XHViM2Q5PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPlx1YjNjNFx1YzJkYyAyXHVjNWQwXHVjMTFjIFx1YjNjNFx1YzJkYyAxXHViODVjIFx1Yzc3NFx1YjNkOTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42PFwvdGQ+XHJcblx0XHRcdDx0ZD5cdWIzYzRcdWMyZGMgMVx1YzVkMFx1YzExYyBcdWIzYzRcdWMyZGMgMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHViM2M0XHVjMmRjIDBcdWM3NTggXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzQ0IFx1YmMyOVx1YmIzODxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHVhYzAwIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1YWMxY1x1YzIxOCBuLCBcdWMyZGNcdWM3OTEgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOCBzdGFydCwgXHVkNzM0XHVhYzAwXHVjNzdjXHVjNzU4IFx1YzIxOCBkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGMgaVx1Yzc1OCBcdWFkMDBcdWFkMTFcdWM5YzAgXHVhYzFjXHVjMjE4XHVhYzAwIDBcdWJjODggXHViM2M0XHVjMmRjXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTVjIFx1YjNjNFx1YzJkYyBcdWM1NDhcdWM3NTggXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWIyOTQgMSwwMDAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWI2MTAsIDAgJmxlOyBkICZsZTsgMm4gKyAmbGZsb29yO25cLzImcmZsb29yO1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHVhYzAwIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWQwMFx1YWQxMVx1YzljMFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDA3NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhvbGlkYXkiLCJkZXNjcmlwdGlvbiI6IjxwPkppYW4tSmlhIGlzIHBsYW5uaW5nIGhpcyBuZXh0IGhvbGlkYXkgaW4gVGFpd2FuLiBEdXJpbmcgaGlzIGhvbGlkYXksIEppYW4tSmlhIG1vdmVzIGZyb20gY2l0eSB0byBjaXR5IGFuZCB2aXNpdHMgYXR0cmFjdGlvbnMgaW4gdGhlIGNpdGllcy48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIG4gY2l0aWVzIGluIFRhaXdhbiwgYWxsIGxvY2F0ZWQgYWxvbmcgYSBzaW5nbGUgaGlnaHdheS4gVGhlIGNpdGllcyBhcmUgbnVtYmVyZWQgY29uc2VjdXRpdmVseSBmcm9tIDAgdG8gbi0xLiBGb3IgY2l0eSBpLCB3aGVyZSAwICZsdDsgaSAmbHQ7IG4tMSwgdGhlIGFkamFjZW50IGNpdGllcyBhcmUgaS0xIGFuZCBpKzEuIFRoZSBvbmx5IGNpdHkgYWRqYWNlbnQgdG8gY2l0eSAwIGlzIGNpdHkgMSwgYW5kIHRoZSBvbmx5IGNpdHkgYWRqYWNlbnQgdG8gY2l0eSBuLTEgaXMgY2l0eSBuLTIuPFwvcD5cclxuXHJcbjxwPkVhY2ggY2l0eSBjb250YWlucyBzb21lIG51bWJlciBvZiBhdHRyYWN0aW9ucy4gSmlhbi1KaWEgaGFzIGRheXMgb2YgaG9saWRheSBhbmQgcGxhbnMgdG8gdmlzaXQgYXMgbWFueSBhdHRyYWN0aW9ucyBhcyBwb3NzaWJsZS4gSmlhbi1KaWEgaGFzIGFscmVhZHkgc2VsZWN0ZWQgYSBjaXR5IGluIHdoaWNoIHRvIHN0YXJ0IGhpcyBob2xpZGF5LiBJbiBlYWNoIGRheSBvZiBoaXMgaG9saWRheSBKaWFuLUppYSBjYW4gZWl0aGVyIG1vdmUgdG8gYW4gYWRqYWNlbnQgY2l0eSwgb3IgZWxzZSB2aXNpdCBhbGwgdGhlIGF0dHJhY3Rpb25zIG9mIHRoZSBjaXR5IGhlIGlzIHN0YXlpbmcsIGJ1dCBub3QgYm90aC4gSmlhbi1KaWEgd2lsbCBuZXZlciB2aXNpdCB0aGUgYXR0cmFjdGlvbnMgaW4gdGhlIHNhbWUgY2l0eSB0d2ljZSBldmVuIGlmIGhlIHN0YXlzIGluIHRoZSBjaXR5IG11bHRpcGxlIHRpbWVzLiBQbGVhc2UgaGVscCBKaWFuLUppYSBwbGFuIGhpcyBob2xpZGF5IHNvIHRoYXQgaGUgdmlzaXRzIGFzIG1hbnkgZGlmZmVyZW50IGF0dHJhY3Rpb25zIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5TdXBwb3NlIEppYW4tSmlhIGhhcyA3IGRheXMgb2YgaG9saWRheSwgdGhlcmUgYXJlIDUgY2l0aWVzIChsaXN0ZWQgaW4gdGhlIHRhYmxlIGJlbG93KSwgYW5kIGhlIHN0YXJ0cyBmcm9tIGNpdHkgMi4gT24gdGhlIGZpcnN0IGRheSBKaWFuLUppYSB2aXNpdHMgdGhlIDIwIGF0dHJhY3Rpb25zIGluIGNpdHkgMi4gT24gdGhlIHNlY29uZCBkYXkgSmlhbi1KaWEgbW92ZXMgZnJvbSBjaXR5IDIgdG8gY2l0eSAzLCBhbmQgb24gdGhlIHRoaXJkIGRheSB2aXNpdHMgdGhlIDMwIGF0dHJhY3Rpb25zIGluIGNpdHkgMy4gSmlhbi1KaWEgdGhlbiBzcGVuZHMgdGhlIG5leHQgdGhyZWUgZGF5cyBtb3ZpbmcgZnJvbSBjaXR5IDMgdG8gY2l0eSAwLCBhbmQgdmlzaXRzIHRoZSAxMCBhdHRyYWN0aW9ucyBpbiBjaXR5IDAgb24gdGhlIHNldmVudGggZGF5LiBUaGUgdG90YWwgbnVtYmVyIG9mIGF0dHJhY3Rpb25zIEppYW4tSmlhIHZpc2l0cyBpcyAyMCArIDMwICsgMTAgPSA2MCwgd2hpY2ggaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIGF0dHJhY3Rpb25zIEppYW4tSmlhIGNhbiB2aXNpdCBpbiA3IGRheXMgd2hlbiBoZSBzdGFydHMgZnJvbSBjaXR5IDIuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoyMCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5jaXR5PFwvdGg+XHJcblx0XHRcdDx0aD5udW1iZXIgb2YgYXR0cmFjdGlvbnM8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjMwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPmRheTxcL3RoPlxyXG5cdFx0XHQ8dGg+YWN0aW9uPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0PFwvdGJvZHk+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+dmlzaXQgdGhlIGF0dHJhY3Rpb25zIGluIGNpdHkgMjxiciBcLz5cclxuXHRcdFx0PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPm1vdmUgZnJvbSBjaXR5IDIgdG8gY2l0eSAzPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPnZpc2l0IHRoZSBhdHRyYWN0aW9ucyBpbiBjaXR5IDM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+bW92ZSBmcm9tIGNpdHkgMyB0byBjaXR5IDI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+bW92ZSBmcm9tIGNpdHkgMiB0byBjaXR5IDE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NjxcL3RkPlxyXG5cdFx0XHQ8dGQ+bW92ZSBmcm9tIGNpdHkgMSB0byBjaXR5IDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+dmlzaXQgdGhlIGF0dHJhY3Rpb25zIGluIGNpdHkgMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+UGxlYXNlIGltcGxlbWVudCBhIGZ1bmN0aW9uIGZpbmRNYXhBdHRyYWN0aW9uIHRoYXQgY29tcHV0ZXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIGF0dHJhY3Rpb25zIEppYW4tSmlhIGNhbiB2aXNpdC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5maW5kTWF4QXR0cmFjdGlvbihuLCBzdGFydCwgZCwgYXR0cmFjdGlvbilcclxuXHQ8dWw+XHJcblx0XHQ8bGk+bjogdGhlIG51bWJlciBvZiBjaXRpZXMuPFwvbGk+XHJcblx0XHQ8bGk+c3RhcnQ6IHRoZSBpbmRleCBvZiB0aGUgc3RhcnRpbmcgY2l0eS48XC9saT5cclxuXHRcdDxsaT5kOiB0aGUgbnVtYmVyIG9mIGRheXMuPFwvbGk+XHJcblx0XHQ8bGk+YXR0cmFjdGlvbjogYXJyYXkgb2YgbGVuZ3RoIG47IGF0dHJhY3Rpb25baV0gaXMgdGhlIG51bWJlciBvZiBhdHRyYWN0aW9ucyBpbiBjaXR5IGksIGZvciAwICZsZTsgaSAmbGU7IG4tMS48XC9saT5cclxuXHRcdDxsaT5UaGUgZnVuY3Rpb24gc2hvdWxkIHJldHVybiB0aGUgbWF4aW11bSBudW1iZXIgb2YgYXR0cmFjdGlvbnMgSmlhbi1KaWEgY2FuIHZpc2l0LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5saW5lIDE6IG4sIHN0YXJ0LCBkLjxcL3NwYW4+PFwvbGk+XHJcblx0PGxpPmxpbmUgMjogYXR0cmFjdGlvblswXSwgLi4uLCBhdHRyYWN0aW9uW24tMV0uPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgcmV0dXJuIHZhbHVlIG9mIGZpbmRNYXhBdHRyYWN0aW9uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2014 6번

  • 문제의 오타를 찾은 사람: kcm1700