시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 64 MB5651136916.312%

문제

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

타이완에는 하나의 고속도로를 따라서 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가 주어진다.

둘째 줄에는 도시 i의 관광지 개수가 0번 도시부터 순서대로 공백으로 구분해 주어진다.

출력

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

서브태스크 1 (7점)

  • 2 ≤ n ≤ 20
  • 한 도시안의 관광지들의 최대 개수 = 1,000,000,000
  • 시작 도시: 제약 없음

서브태스크 2 (23점)

  • 2 ≤ n ≤ 100,000
  • 한 도시안의 관광지들의 최대 개수 = 100
  • 시작 도시: 도시 0

서브태스크 3 (17점)

  • 2 ≤ n ≤ 3,000
  • 한 도시안의 관광지들의 최대 개수 = 1,000,000,000
  • 시작 도시: 제약 없음

서브태스크 4 (53점)

  • 2 ≤ n ≤ 100,000
  • 한 도시안의 관광지들의 최대 개수 = 1,000,000,000
  • 시작 도시: 제약 없음

예제 입력 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+XHVjOWMwXHVjNTQ4XHVjOWMwXHVjNTQ0XHVhYzAwIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1YWMxY1x1YzIxOCBuLCBcdWMyZGNcdWM3OTEgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOCBzdGFydCwgXHVkNzM0XHVhYzAwXHVjNzdjXHVjNzU4IFx1YzIxOCBkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGMgaVx1Yzc1OCBcdWFkMDBcdWFkMTFcdWM5YzAgXHVhYzFjXHVjMjE4XHVhYzAwIDBcdWJjODggXHViM2M0XHVjMmRjXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5YzBcdWM1NDhcdWM5YzBcdWM1NDRcdWFjMDAgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDAwXHVhZDExXHVjOWMwXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4yICZsZTsgbiAmbGU7IDIwPFwvbGk+XHJcblx0PGxpPlx1ZDU1YyBcdWIzYzRcdWMyZGNcdWM1NDhcdWM3NTggXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMTggPSAxLDAwMCwwMDAsMDAwPFwvbGk+XHJcblx0PGxpPlx1YzJkY1x1Yzc5MSBcdWIzYzRcdWMyZGM6IFx1YzgxY1x1YzU3ZCBcdWM1YzZcdWM3NGM8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHVsPlxyXG5cdDxsaT4yICZsZTsgbiAmbGU7IDEwMCwwMDA8XC9saT5cclxuXHQ8bGk+XHVkNTVjIFx1YjNjNFx1YzJkY1x1YzU0OFx1Yzc1OCBcdWFkMDBcdWFkMTFcdWM5YzBcdWI0ZTRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOCA9IDEwMDxcL2xpPlxyXG5cdDxsaT5cdWMyZGNcdWM3OTEgXHViM2M0XHVjMmRjOiBcdWIzYzRcdWMyZGMgMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8dWw+XHJcblx0PGxpPjIgJmxlOyBuICZsZTsgMywwMDA8XC9saT5cclxuXHQ8bGk+XHVkNTVjIFx1YjNjNFx1YzJkY1x1YzU0OFx1Yzc1OCBcdWFkMDBcdWFkMTFcdWM5YzBcdWI0ZTRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOCA9IDEsMDAwLDAwMCwwMDA8XC9saT5cclxuXHQ8bGk+XHVjMmRjXHVjNzkxIFx1YjNjNFx1YzJkYzogXHVjODFjXHVjNTdkIFx1YzVjNlx1Yzc0YzxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazQiOiI8dWw+XHJcblx0PGxpPjIgJmxlOyBuICZsZTsgMTAwLDAwMDxcL2xpPlxyXG5cdDxsaT5cdWQ1NWMgXHViM2M0XHVjMmRjXHVjNTQ4XHVjNzU4IFx1YWQwMFx1YWQxMVx1YzljMFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4ID0gMSwwMDAsMDAwLDAwMDxcL2xpPlxyXG5cdDxsaT5cdWMyZGNcdWM3OTEgXHViM2M0XHVjMmRjOiBcdWM4MWNcdWM1N2QgXHVjNWM2XHVjNzRjPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJjdXN0b21fc3VidGFza19zY29yaW5nX2IiOiI8cD5cdWJhYThcdWI0ZTAgXHViZDgwXHViZDg0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYywgMCAmbGU7IGQgJmxlOyAybiArICZsZmxvb3I7blwvMiZyZmxvb3I7XHVjNzc0XHVhY2UwLFx1MDAxZFx1YWMwMSBcdWIzYzRcdWMyZGNcdWM3NTggXHVhZDAwXHVhZDExXHVjOWMwXHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIxMDA3NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhvbGlkYXkiLCJkZXNjcmlwdGlvbiI6IjxwPkppYW4tSmlhIGlzIHBsYW5uaW5nIGhpcyBuZXh0IGhvbGlkYXkgaW4gVGFpd2FuLiBEdXJpbmcgaGlzIGhvbGlkYXksIEppYW4tSmlhIG1vdmVzIGZyb20gY2l0eSB0byBjaXR5IGFuZCB2aXNpdHMgYXR0cmFjdGlvbnMgaW4gdGhlIGNpdGllcy48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIG4gY2l0aWVzIGluIFRhaXdhbiwgYWxsIGxvY2F0ZWQgYWxvbmcgYSBzaW5nbGUgaGlnaHdheS4gVGhlIGNpdGllcyBhcmUgbnVtYmVyZWQgY29uc2VjdXRpdmVseSBmcm9tIDAgdG8gbi0xLiBGb3IgY2l0eSBpLCB3aGVyZSAwICZsdDsgaSAmbHQ7IG4tMSwgdGhlIGFkamFjZW50IGNpdGllcyBhcmUgaS0xIGFuZCBpKzEuIFRoZSBvbmx5IGNpdHkgYWRqYWNlbnQgdG8gY2l0eSAwIGlzIGNpdHkgMSwgYW5kIHRoZSBvbmx5IGNpdHkgYWRqYWNlbnQgdG8gY2l0eSBuLTEgaXMgY2l0eSBuLTIuPFwvcD5cclxuXHJcbjxwPkVhY2ggY2l0eSBjb250YWlucyBzb21lIG51bWJlciBvZiBhdHRyYWN0aW9ucy4gSmlhbi1KaWEgaGFzIGRheXMgb2YgaG9saWRheSBhbmQgcGxhbnMgdG8gdmlzaXQgYXMgbWFueSBhdHRyYWN0aW9ucyBhcyBwb3NzaWJsZS4gSmlhbi1KaWEgaGFzIGFscmVhZHkgc2VsZWN0ZWQgYSBjaXR5IGluIHdoaWNoIHRvIHN0YXJ0IGhpcyBob2xpZGF5LiBJbiBlYWNoIGRheSBvZiBoaXMgaG9saWRheSBKaWFuLUppYSBjYW4gZWl0aGVyIG1vdmUgdG8gYW4gYWRqYWNlbnQgY2l0eSwgb3IgZWxzZSB2aXNpdCBhbGwgdGhlIGF0dHJhY3Rpb25zIG9mIHRoZSBjaXR5IGhlIGlzIHN0YXlpbmcsIGJ1dCBub3QgYm90aC4gSmlhbi1KaWEgd2lsbCBuZXZlciB2aXNpdCB0aGUgYXR0cmFjdGlvbnMgaW4gdGhlIHNhbWUgY2l0eSB0d2ljZSBldmVuIGlmIGhlIHN0YXlzIGluIHRoZSBjaXR5IG11bHRpcGxlIHRpbWVzLiBQbGVhc2UgaGVscCBKaWFuLUppYSBwbGFuIGhpcyBob2xpZGF5IHNvIHRoYXQgaGUgdmlzaXRzIGFzIG1hbnkgZGlmZmVyZW50IGF0dHJhY3Rpb25zIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5TdXBwb3NlIEppYW4tSmlhIGhhcyA3IGRheXMgb2YgaG9saWRheSwgdGhlcmUgYXJlIDUgY2l0aWVzIChsaXN0ZWQgaW4gdGhlIHRhYmxlIGJlbG93KSwgYW5kIGhlIHN0YXJ0cyBmcm9tIGNpdHkgMi4gT24gdGhlIGZpcnN0IGRheSBKaWFuLUppYSB2aXNpdHMgdGhlIDIwIGF0dHJhY3Rpb25zIGluIGNpdHkgMi4gT24gdGhlIHNlY29uZCBkYXkgSmlhbi1KaWEgbW92ZXMgZnJvbSBjaXR5IDIgdG8gY2l0eSAzLCBhbmQgb24gdGhlIHRoaXJkIGRheSB2aXNpdHMgdGhlIDMwIGF0dHJhY3Rpb25zIGluIGNpdHkgMy4gSmlhbi1KaWEgdGhlbiBzcGVuZHMgdGhlIG5leHQgdGhyZWUgZGF5cyBtb3ZpbmcgZnJvbSBjaXR5IDMgdG8gY2l0eSAwLCBhbmQgdmlzaXRzIHRoZSAxMCBhdHRyYWN0aW9ucyBpbiBjaXR5IDAgb24gdGhlIHNldmVudGggZGF5LiBUaGUgdG90YWwgbnVtYmVyIG9mIGF0dHJhY3Rpb25zIEppYW4tSmlhIHZpc2l0cyBpcyAyMCArIDMwICsgMTAgPSA2MCwgd2hpY2ggaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIGF0dHJhY3Rpb25zIEppYW4tSmlhIGNhbiB2aXNpdCBpbiA3IGRheXMgd2hlbiBoZSBzdGFydHMgZnJvbSBjaXR5IDIuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoyMCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5jaXR5PFwvdGg+XHJcblx0XHRcdDx0aD5udW1iZXIgb2YgYXR0cmFjdGlvbnM8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjEwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjMwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPmRheTxcL3RoPlxyXG5cdFx0XHQ8dGg+YWN0aW9uPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0PFwvdGJvZHk+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+dmlzaXQgdGhlIGF0dHJhY3Rpb25zIGluIGNpdHkgMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD5tb3ZlIGZyb20gY2l0eSAyIHRvIGNpdHkgMzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD52aXNpdCB0aGUgYXR0cmFjdGlvbnMgaW4gY2l0eSAzPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPm1vdmUgZnJvbSBjaXR5IDMgdG8gY2l0eSAyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPm1vdmUgZnJvbSBjaXR5IDIgdG8gY2l0eSAxPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjY8XC90ZD5cclxuXHRcdFx0PHRkPm1vdmUgZnJvbSBjaXR5IDEgdG8gY2l0eSAwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPnZpc2l0IHRoZSBhdHRyYWN0aW9ucyBpbiBjaXR5IDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlBsZWFzZSBpbXBsZW1lbnQgYSBmdW5jdGlvbiBmaW5kTWF4QXR0cmFjdGlvbiB0aGF0IGNvbXB1dGVzIHRoZSBtYXhpbXVtIG51bWJlciBvZiBhdHRyYWN0aW9ucyBKaWFuLUppYSBjYW4gdmlzaXQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+ZmluZE1heEF0dHJhY3Rpb24obiwgc3RhcnQsIGQsIGF0dHJhY3Rpb24pXHJcblx0PHVsPlxyXG5cdFx0PGxpPm46IHRoZSBudW1iZXIgb2YgY2l0aWVzLjxcL2xpPlxyXG5cdFx0PGxpPnN0YXJ0OiB0aGUgaW5kZXggb2YgdGhlIHN0YXJ0aW5nIGNpdHkuPFwvbGk+XHJcblx0XHQ8bGk+ZDogdGhlIG51bWJlciBvZiBkYXlzLjxcL2xpPlxyXG5cdFx0PGxpPmF0dHJhY3Rpb246IGFycmF5IG9mIGxlbmd0aCBuOyBhdHRyYWN0aW9uW2ldIGlzIHRoZSBudW1iZXIgb2YgYXR0cmFjdGlvbnMgaW4gY2l0eSBpLCBmb3IgMCAmbGU7IGkgJmxlOyBuLTEuPFwvbGk+XHJcblx0XHQ8bGk+VGhlIGZ1bmN0aW9uIHNob3VsZCByZXR1cm4gdGhlIG1heGltdW0gbnVtYmVyIG9mIGF0dHJhY3Rpb25zIEppYW4tSmlhIGNhbiB2aXNpdC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+bGluZSAxOiBuLCBzdGFydCwgZC48XC9zcGFuPjxcL2xpPlxyXG5cdDxsaT5saW5lIDI6IGF0dHJhY3Rpb25bMF0sIC4uLiwgYXR0cmFjdGlvbltuLTFdLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIHJldHVybiB2YWx1ZSBvZiBmaW5kTWF4QXR0cmFjdGlvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic3VidGFzazEiOiI8dWw+XHJcblx0PGxpPjIgJmxlOyBuICZsZTsgMjA8XC9saT5cclxuXHQ8bGk+bWF4aW11bSBudW1iZXIgb2YgYXR0cmFjdGlvbnMgaW4gYSBjaXR5ID0gMSwwMDAsMDAwLDAwMDxcL2xpPlxyXG5cdDxsaT5zdGFydGluZyBjaXR5OiZuYnNwO25vIGNvbnN0cmFpbnRzPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MiAmbGU7IG4gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPm1heGltdW0gbnVtYmVyIG9mIGF0dHJhY3Rpb25zIGluIGEgY2l0eSA9IDEwMDxcL2xpPlxyXG5cdDxsaT5zdGFydGluZyBjaXR5OiZuYnNwO2NpdHkgMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8dWw+XHJcblx0PGxpPjIgJmxlOyBuICZsZTsgMywwMDA8XC9saT5cclxuXHQ8bGk+bWF4aW11bSBudW1iZXIgb2YgYXR0cmFjdGlvbnMgaW4gYSBjaXR5ID0gMSwwMDAsMDAwLDAwMDxcL2xpPlxyXG5cdDxsaT5zdGFydGluZyBjaXR5OiZuYnNwO25vIGNvbnN0cmFpbnRzPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrNCI6Ijx1bD5cclxuXHQ8bGk+MiAmbGU7IG4gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPm1heGltdW0gbnVtYmVyIG9mIGF0dHJhY3Rpb25zIGluIGEgY2l0eSA9IDEsMDAwLDAwMCwwMDA8XC9saT5cclxuXHQ8bGk+c3RhcnRpbmcgY2l0eTombmJzcDtubyBjb25zdHJhaW50czxcL2xpPlxyXG48XC91bD5cclxuIiwiY3VzdG9tX3N1YnRhc2tfc2NvcmluZ19iIjoiPHA+SW4gYWxsIHN1YnRhc2tzIDAgJmxlOyBkICZsZTsgMm4gKyAmbGZsb29yO25cLzImcmZsb29yOywgYW5kIHRoZSBudW1iZXIgb2YgYXR0cmFjdGlvbnMgaW4gZWFjaCBjaXR5IGlzIG5vbm5lZ2F0aXZlLjxcL3A+XHJcbiJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2014 > Day 2 6번

  • 문제의 오타를 찾은 사람: kcm1700
  • 문제를 만든 사람: Jakub Łącki

채점 및 기타 정보

  • 예제는 채점하지 않는다.