시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 169 28 16 47.059%

문제

사진: 풍선으로 하늘에 띄운 집. 2018 KAIST RUN Spring Contest 포스터에도 사용된 사진이다.

서기 2117년, 유재민 교수에 의해 TSP (Traveling Salesperson Problem)의 선형시간 알고리즘이 개발되었다. 얼마 가지 않아 모든 컴퓨터 시스템은 붕괴되었고, 세상은 핵무기로 인해 황폐화 되었다. 컴퓨터 과학의 최고 전문가이던 당신 역시도 할 일을 잃게 되었고, 절망 속에 인생의 의미를 잃어버린 지 오래다. 과연 그동안 당신의 심장을 뛰게 하던 모든 것들은 어디로 갔을까? 끝없이 자신에게 질문한 끝에 내린 결론은...

"ICPC를 처음 시작한 그 때 그 카이스트를 가면, 내 인생의 의미를 찾을 수 있지 않을까?"

도로망이나 철도는 모두 황폐화된지 오래이다. 그렇지만 열렬한 ICPC 참가자였던 당신은 100년 전 대전 대회에서 받았던 풍선을 여전히 가지고 있다. 만약 그 풍선으로 집을 띄울 수만 있다면...

현재 당신에게는 N개의 풍선이 있고, 당신은 풍선을 하나씩 지붕에 매달아서 집을 하늘로 띄우려 한다. 각각의 풍선은 고도 제한 Li와 용량 Di가 있는데, 이는 기압의 영향으로 인하여 고도 Li 이하에서만 이 풍선을 불 수 있고, 이 풍선은 고도를 Di만큼 상승시킨 후 터진다는 것을 뜻한다.

당신의 여정은 고도 0에서 출발한다. 부풀어 있는 풍선이 2개 이상이면 집이 너무 빠른 속도로 상승할 수 있으니, 당신은 하나의 풍선을 불어서 지붕에 매단 후, 풍선이 터질 때가지 고도를 상승시키고, 터진 이후에 또 하나의 풍선을 불어서 터질 때까지 고도를 상승시키는 것을 반복해서 집을 띄울 예정이다. 편의상 터진 이후 풍선을 매다는 동안의 고도 변화는 없다고 가정한다. (즉, 풍선만이 유일하게 고도를 바꿀 수 있다.)

최종 고도는 어느 위치던 간에 상관 없으나, 하나의 풍선은 터지기 전 까지 일정한 거리를 움직일 수 있으니, 최대한 많은 풍선을 터뜨리는 것이 좋다. 고로 당신은 터뜨릴 수 있는 풍선의 최대 개수를 계산한 후, 정말 KAIST로의 여행을 떠날 수 있는지를 계산해 보려고 한다. 100년 전의 ICPC 경험이, 이 문제를 해결하는 데 정말 도움을 줄 수 있을까?

입력

첫 번째 줄에 풍선의 개수 N이 주어진다.

이후 N개의 줄의 i번째 줄에는 풍선의 고도 제한 Li와 풍선의 용량 Di를 의미하는 정수 2개가 공백으로 구분되어 주어진다.

출력

터뜨릴 수 있는 풍선의 최대 개수를 출력하여라.

제한

  • 1 ≤ N ≤ 250,000
  • 0 ≤ Li ≤ 1015
  • 1 ≤ Di ≤ 109

서브태스크 1 (22점)

이 서브태스크는 다음의 조건을 만족한다.:

  • N ≤ 20

서브태스크 2 (33점)

이 서브태스크는 다음의 조건을 만족한다.:

  • N ≤ 5,000

서브태스크 3 (45점)

이 서브태스크는 추가 제한 조건이 없다.

예제 입력 1

3
1 4
1 5
9 2

예제 출력 1

2

예제 입력 2

4
0 1
0 2
0 3
0 4

예제 출력 2

1
W3sicHJvYmxlbV9pZCI6IjE1NzczIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVG91Y2ggVGhlIFNreSIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTU3NzNcL3RvdWNoLmpwZ1wiIHN0eWxlPVwid2lkdGg6IDY3NXB4OyBoZWlnaHQ6IDQ1MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdWMwYWNcdWM5YzQ6IFx1ZDQ4ZFx1YzEyMFx1YzczY1x1Yjg1YyBcdWQ1NThcdWIyOThcdWM1ZDAgXHViNzQ0XHVjNmI0IFx1YzlkMS4gMjAxOCBLQUlTVCBSVU4gU3ByaW5nIENvbnRlc3QgXHVkM2VjXHVjMmE0XHVkMTMwXHVjNWQwXHViM2M0IFx1YzBhY1x1YzZhOVx1YjQxYyBcdWMwYWNcdWM5YzRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzExY1x1YWUzMCAyMTE3XHViMTQ0LCBcdWM3MjBcdWM3YWNcdWJiZmMgXHVhZDUwXHVjMjE4XHVjNWQwIFx1Yzc1OFx1ZDU3NCBUU1AgKFRyYXZlbGluZyBTYWxlc3BlcnNvbiBQcm9ibGVtKVx1Yzc1OCBcdWMxMjBcdWQ2MTVcdWMyZGNcdWFjMDQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzc0IFx1YWMxY1x1YmMxY1x1YjQxOFx1YzVjOFx1YjJlNC4gXHVjNWJjXHViOWM4IFx1YWMwMFx1YzljMCBcdWM1NGFcdWM1NDQgXHViYWE4XHViNGUwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWMyZGNcdWMyYTRcdWQxNWNcdWM3NDAgXHViZDk1XHVhZDM0XHViNDE4XHVjNWM4XHVhY2UwLCBcdWMxMzhcdWMwYzFcdWM3NDAgXHVkNTc1XHViYjM0XHVhZTMwXHViODVjIFx1Yzc3OFx1ZDU3NCBcdWQ2NjlcdWQzZDBcdWQ2NTQgXHViNDE4XHVjNWM4XHViMmU0LiBcdWNlZjRcdWQ0ZThcdWQxMzAgXHVhY2ZjXHVkNTU5XHVjNzU4IFx1Y2Q1Y1x1YWNlMCBcdWM4MDRcdWJiMzhcdWFjMDBcdWM3NzRcdWIzNTggXHViMmY5XHVjMmUwIFx1YzVlZFx1YzJkY1x1YjNjNCBcdWQ1NjAgXHVjNzdjXHVjNzQ0IFx1Yzc4M1x1YWM4YyBcdWI0MThcdWM1YzhcdWFjZTAsIFx1YzgwOFx1YjlkZCBcdWMxOGRcdWM1ZDAgXHVjNzc4XHVjMGRkXHVjNzU4IFx1Yzc1OFx1YmJmOFx1Yjk3YyBcdWM3ODNcdWM1YjRcdWJjODRcdWI5YjAgXHVjOWMwIFx1YzYyNFx1Yjc5OFx1YjJlNC4gXHVhY2ZjXHVjNWYwIFx1YWRmOFx1YjNkOVx1YzU0OCBcdWIyZjlcdWMyZTBcdWM3NTggXHVjMmVjXHVjN2E1XHVjNzQ0IFx1YjZmMFx1YWM4YyBcdWQ1NThcdWIzNTggXHViYWE4XHViNGUwIFx1YWM4M1x1YjRlNFx1Yzc0MCBcdWM1YjRcdWI1MTRcdWI4NWMgXHVhYzE0XHVjNzQ0XHVhZTRjPyBcdWIwNWRcdWM1YzZcdWM3NzQgXHVjNzkwXHVjMmUwXHVjNWQwXHVhYzhjIFx1YzljOFx1YmIzOFx1ZDU1YyBcdWIwNWRcdWM1ZDAgXHViMGI0XHViOWIwIFx1YWNiMFx1Yjg2MFx1Yzc0MC4uLjxcL3A+XHJcblxyXG48cD48ZW0+JnF1b3Q7SUNQQ1x1Yjk3YyBcdWNjOThcdWM3NGMgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YWRmOCBcdWI1NGMgXHVhZGY4IFx1Y2U3NFx1Yzc3NFx1YzJhNFx1ZDJiOFx1Yjk3YyBcdWFjMDBcdWJhNzQsIFx1YjBiNCBcdWM3NzhcdWMwZGRcdWM3NTggXHVjNzU4XHViYmY4XHViOTdjIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0NFx1YWU0Yz8mcXVvdDs8XC9lbT48XC9wPlxyXG5cclxuPHA+XHViM2M0XHViODVjXHViOWRkXHVjNzc0XHViMDk4IFx1Y2NhMFx1YjNjNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVkNjY5XHVkM2QwXHVkNjU0XHViNDFjXHVjOWMwIFx1YzYyNFx1Yjc5OFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwXHViOWNjIFx1YzVmNFx1YjgyY1x1ZDU1YyBJQ1BDIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YzYwMFx1YjM1OCBcdWIyZjlcdWMyZTBcdWM3NDAgMTAwXHViMTQ0IFx1YzgwNCBcdWIzMDBcdWM4MDQgXHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFx1YmMxYlx1YzU1OFx1YjM1OCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVjNWVjXHVjODA0XHVkNzg4IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFkZjggXHVkNDhkXHVjMTIwXHVjNzNjXHViODVjIFx1YzlkMVx1Yzc0NCBcdWI3NDRcdWM2YjggXHVjMjE4XHViOWNjIFx1Yzc4OFx1YjJlNFx1YmE3NC4uLjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMgXHViMmY5XHVjMmUwXHVjNWQwXHVhYzhjXHViMjk0IDxlbT5OPFwvZW0+XHVhYzFjXHVjNzU4IFx1ZDQ4ZFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzljMFx1YmQ5NVx1YzVkMCBcdWI5ZTRcdWIyZWNcdWM1NDRcdWMxMWMgXHVjOWQxXHVjNzQ0IFx1ZDU1OFx1YjI5OFx1Yjg1YyBcdWI3NDRcdWM2YjBcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNDhkXHVjMTIwXHVjNzQwIFx1YWNlMFx1YjNjNCBcdWM4MWNcdWQ1NWMgPGVtPkw8c3ViPmk8XC9zdWI+PFwvZW0+XHVjNjQwIFx1YzZhOVx1YjdjOSA8ZW0+RDxzdWI+aTxcL3N1Yj48XC9lbT5cdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgXHVhZTMwXHVjNTU1XHVjNzU4IFx1YzYwMVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzhcdWQ1NThcdWM1ZWMgXHVhY2UwXHViM2M0IDxlbT5MPHN1Yj5pPFwvc3ViPjxcL2VtPiZuYnNwO1x1Yzc3NFx1ZDU1OFx1YzVkMFx1YzExY1x1YjljYyBcdWM3NzQgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YmQ4OCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVkNDhkXHVjMTIwXHVjNzQwIFx1YWNlMFx1YjNjNFx1Yjk3YyA8ZW0+RDxzdWI+aTxcL3N1Yj48XC9lbT5cdWI5Y2NcdWQwN2MgXHVjMGMxXHVjMmI5XHVjMmRjXHVkMGE4IFx1ZDZjNCBcdWQxMzBcdWM5YzRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzU4IFx1YzVlY1x1YzgxNVx1Yzc0MCBcdWFjZTBcdWIzYzQgMFx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NWNcdWIyZTQuIFx1YmQ4MFx1ZDQ4MFx1YzViNCBcdWM3ODhcdWIyOTQgXHVkNDhkXHVjMTIwXHVjNzc0IDJcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzc0XHViYTc0IFx1YzlkMVx1Yzc3NCBcdWIxMDhcdWJiMzQgXHViZTYwXHViOTc4IFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWMwYzFcdWMyYjlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YjJjOCwgXHViMmY5XHVjMmUwXHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHViZDg4XHVjNWI0XHVjMTFjIFx1YzljMFx1YmQ5NVx1YzVkMCBcdWI5ZTRcdWIyZTggXHVkNmM0LCBcdWQ0OGRcdWMxMjBcdWM3NzQgXHVkMTMwXHVjOWM4IFx1YjU0Y1x1YWMwMFx1YzljMCBcdWFjZTBcdWIzYzRcdWI5N2MgXHVjMGMxXHVjMmI5XHVjMmRjXHVkMGE0XHVhY2UwLCBcdWQxMzBcdWM5YzQgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YjYxMCBcdWQ1NThcdWIwOThcdWM3NTggXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YmQ4OFx1YzViNFx1YzExYyBcdWQxMzBcdWM5YzggXHViNTRjXHVhZTRjXHVjOWMwIFx1YWNlMFx1YjNjNFx1Yjk3YyBcdWMwYzFcdWMyYjlcdWMyZGNcdWQwYTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU3NFx1YzExYyBcdWM5ZDFcdWM3NDQgXHViNzQ0XHVjNmI4IFx1YzYwOFx1YzgxNVx1Yzc3NFx1YjJlNC4gXHVkM2I4XHVjNzU4XHVjMGMxIFx1ZDEzMFx1YzljNCBcdWM3NzRcdWQ2YzQgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjllNFx1YjJlNFx1YjI5NCBcdWIzZDlcdWM1NDhcdWM3NTggXHVhY2UwXHViM2M0IFx1YmNjMFx1ZDY1NFx1YjI5NCBcdWM1YzZcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LiAoXHVjOTg5LCBcdWQ0OGRcdWMxMjBcdWI5Y2NcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YWNlMFx1YjNjNFx1Yjk3YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1Y2Q1Y1x1Yzg4NSBcdWFjZTBcdWIzYzRcdWIyOTQgXHVjNWI0XHViMjkwIFx1YzcwNFx1Y2U1OFx1YjM1OCBcdWFjMDRcdWM1ZDAgXHVjMGMxXHVhZDAwIFx1YzVjNlx1YzczY1x1YjA5OCwgXHVkNTU4XHViMDk4XHVjNzU4IFx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWQxMzBcdWM5YzBcdWFlMzAgXHVjODA0IFx1YWU0Y1x1YzljMCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVhYzcwXHViOWFjXHViOTdjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHVjNzNjXHViMmM4LCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWQxMzBcdWI3MjhcdWI5YWNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1Yzg4Ylx1YjJlNC4gXHVhY2UwXHViODVjIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWQxMzBcdWI3MjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NWMgXHVkNmM0LCBcdWM4MTVcdWI5ZDAgS0FJU1RcdWI4NWNcdWM3NTggXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YjVhMFx1YjBhMCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU3NCBcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiAxMDBcdWIxNDQgXHVjODA0XHVjNzU4IElDUEMgXHVhY2JkXHVkNWQ4XHVjNzc0LCBcdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVjODE1XHViOWQwIFx1YjNjNFx1YzZjMFx1Yzc0NCBcdWM5MDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTggPGVtPk48XC9lbT5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgPGVtPk48XC9lbT5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNzU4IDxlbT5pPFwvZW0+XHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ0OGRcdWMxMjBcdWM3NTggXHVhY2UwXHViM2M0IFx1YzgxY1x1ZDU1YyA8ZW0+TDxzdWI+aTxcL3N1Yj48XC9lbT5cdWM2NDAgXHVkNDhkXHVjMTIwXHVjNzU4IFx1YzZhOVx1YjdjOSA8ZW0+RDxzdWI+aTxcL3N1Yj48XC9lbT5cdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOCAyXHVhYzFjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDEzMFx1YjcyOFx1YjliNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDQ4ZFx1YzEyMFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IDxlbT5OPFwvZW0+ICZsZTsgMjUwLDAwMDxcL2xpPlxyXG5cdDxsaT4wICZsZTsgPGVtPkw8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgMTA8c3VwPjE1PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgPGVtPkQ8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPlx1Yzc3NCBcdWMxMWNcdWJlMGNcdWQwZGNcdWMyYTRcdWQwNmNcdWIyOTQgXHViMmU0XHVjNzRjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxlbT5OPFwvZW0+ICZsZTsgMjA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjNzc0IFx1YzExY1x1YmUwY1x1ZDBkY1x1YzJhNFx1ZDA2Y1x1YjI5NCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC46PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGVtPk48XC9lbT4gJmxlOyA1LDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8cD5cdWM3NzQgXHVjMTFjXHViZTBjXHVkMGRjXHVjMmE0XHVkMDZjXHViMjk0IFx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWQ1NWMgXHVjODcwXHVhYzc0XHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNTc3MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRvdWNoIFRoZSBTa3kiLCJkZXNjcmlwdGlvbiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzE1NzczXC90b3VjaC5qcGdcIiBzdHlsZT1cIndpZHRoOiA2NzVweDsgaGVpZ2h0OiA0NTBweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlOiBUaGUgaG91c2UgZmxvYXRzIHVwIGluIHRoZSBza3kgYnkgYmFsbG9vbnMuIFRoaXMgcGljdHVyZSBpcyBhbHNvIHVzZWQgaW4gMjAxOCBLQUlTVCBSVU4gU3ByaW5nIENvbnRlc3QgcG9zdGVyLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgeWVhciAyMTE3LCBQcm9mZXNzb3IgSmFlbWluIFl1IGRldmVsb3BlZCBhIGxpbmVhci10aW1lIGFsZ29yaXRobSBmb3IgVFNQKFRyYXZlbGluZyBTYWxlc3BlcnNvbiBQcm9ibGVtKS4gTm90IGxvbmcgYWZ0ZXIgdGhhdCBoYXBwZW5lZCwgYWxsIGNvbXB1dGVyIHN5c3RlbXMgd2VyZSBkZXN0cm95ZWQsIGFuZCBudWNsZWFyIHdlYXBvbnMgZGVtb2xpc2hlZCBhbGwgdGhlIGxhbmRzLiBZb3UsIGEgZ3JlYXQgY29tcHV0ZXIgZXhwZXJ0LCBhbHNvIGxvc3QgeW91ciBqb2IuIFdpdGggYSBncmVhdCBkZXNwYWlyLCB5b3UgbG9zdCB5b3VyIG1lYW5pbmcgb2YgbGlmZSBsb25nIGFnby4gQWxsIHRob3NlIHRoaW5ncyB0aGF0IG1hZGUgeW91ciBoZWFydCBiZWF0IC0tIHdoZXJlIGhhZCB0aGV5IGdvbmU/IEFmdGVyIHF1ZXN0aW9uaW5nIHlvdXJzZWxmIGFnYWluIGFuZCBhZ2FpbiwgeW91ciBjb25jbHVzaW9uIGlzIC4uLjxcL3A+XHJcblxyXG48cD48ZW0+JnF1b3Q7SWYgSSBnbyB0byBLQUlTVCB3aGVyZSBJIHN0YXJ0ZWQgbXkgZmlyc3QgSUNQQywgY2FuIEkgZmluZCBhIG1lYW5pbmcgb2YgbXkgbGlmZT8mcXVvdDs8XC9lbT48XC9wPlxyXG5cclxuPHA+QWxsIHRyYW5zcG9ydGF0aW9ucyB3ZXJlIGRlc3Ryb3llZCwgYnV0IHlvdSB3ZXJlIGFuIGF2aWQgSUNQQyBwYXJ0aWNpcGFudCwgYW5kIHlvdSBjb2xsZWN0ZWQgYSBsb3Qgb2YgY2VudHVyeS1vbGQgYmFsbG9vbnMgaW4gS29yZWFuIFJlZ2lvbmFscy4gSWYgeW91IGNvdWxkIGZsb2F0IGEgaG91c2Ugd2l0aCBzb21lIG9mIHRob3NlIGJhbGxvb25zLi4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkN1cnJlbnRseSB5b3UgaGF2ZSA8ZW0+TjxcL2VtPiZuYnNwO2JhbGxvb25zLCBhbmQgeW91IGFyZSB0cnlpbmcgdG8gZmxvYXQgdGhlIGhvdXNlIGludG8gdGhlIHNreSBieSBhdHRhY2hpbmcgYmFsbG9vbnMgb24gdGhlIHJvb2Z0b3AuIEV2ZXJ5IGJhbGxvb24gaGF2ZSBhbHRpdHVkZSBsaW1pdCA8ZW0+TDxzdWI+aTxcL3N1Yj48XC9lbT4mbmJzcDthbmQgY2FwYWNpdHkgPGVtPkQ8c3ViPmk8XC9zdWI+PFwvZW0+LCB3aGljaCBpbmRpY2F0ZXMgeW91IGNhbiBibG93IGJhbGxvb25zIGluIGFsdGl0dWRlIGF0IG1vc3QgPGVtPkw8c3ViPmk8XC9zdWI+PFwvZW0+LCBhbmQgdGhlIGJhbGxvb24gYnVzdHMgYWZ0ZXIgaW5jcmVhc2luZyB0aGUgYWx0aXR1ZGUgYnkgPGVtPkQ8c3ViPmk8XC9zdWI+PFwvZW0+LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3VyIGpvdXJuZXkgc3RhcnRzIGF0IGFsdGl0dWRlIDAuIElmIHlvdSBoYXZlIG1vcmUgdGhhbiAxIGJhbGxvb25zIGVubGFyZ2VkLCB0aGVuIHRoZSBob3VzZSB3aWxsIGFzY2VuZCB0b28gZmFzdC4gVGh1cywgeW91IHdpbGwgYmxvdyBvbmUgYmFsbG9vbiBhbmQgYXR0YWNoIGl0IGF0IHRoZSByb29mdG9wLCBpbmNyZWFzZSB0aGUgYWx0aXR1ZGUgdW50aWwgdGhlIGJhbGxvb25zIGJ1c3QsIGJsb3cgdGhlIG90aGVyIGJhbGxvb24gYW5kIGF0dGFjaCBpdCB0byBpbmNyZWFzZSB0aGUgYWx0aXR1ZGUuLi4gdG8gbWFrZSB5b3VyIGhvdXNlIGZsb2F0LiBGb3IgY29udmVuaWVuY2UsIHlvdSBtYXkgYXNzdW1lIHRoYXQgPHN0cm9uZz5iYWxsb29ucyBjYW4gb25seSBpbmNyZWFzZSB0aGUgYWx0aXR1ZGU8XC9zdHJvbmc+LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgZG9uJiMzOTt0IGNhcmUgYWJvdXQgeW91ciBmaW5hbCBhbHRpdHVkZSwgYnV0IGEgYmFsbG9vbiBjYW4gbW92ZSBhIGZpeGVkIGFtb3VudCBvZiBkaXN0YW5jZS4gVGh1cywgeW91IHdhbnQgdG8gYnVzdCBhcyBtYW55IGJhbGxvb25zIGFzIHBvc3NpYmxlLiBZb3Ugd2FudCB0byBjYWxjdWxhdGUgYSBtYXhpbXVtIG51bWJlciBvZiBiYWxsb29ucyB5b3UgY2FuIGJ1c3QsIGFuZCBjaGVjayBpZiB5b3UgY2FuIG1ha2UgYSBqb3VybmV5IHRvIEtBSVNULiBMZXQmIzM5O3Mgc2VlIHdoZXRoZXIgeW91ciAxMDAteWVhci1vbGQgSUNQQyBleHBlcmllbmNlIGNhbiBoZWxwIG9uIHRoaXMgcHJvYmxlbSE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIDxlbT5OPFwvZW0+LCB0aGUgbnVtYmVyIG9mIGJhbGxvb25zLjxcL3A+XHJcblxyXG48cD5JbiBuZXh0IDxlbT5OPFwvZW0+Jm5ic3A7bGluZXMsIHRoZSBhbHRpdHVkZSBsaW1pdCBvZiA8ZW0+aTxcL2VtPi10aCBiYWxsb29uIDxlbT5MPHN1Yj5pPFwvc3ViPjxcL2VtPiwgYW5kIGNhcGFjaXR5IG9mIDxlbT5pPFwvZW0+LXRoIGJhbGxvb24gPGVtPkQ8c3ViPmk8XC9zdWI+PFwvZW0+Jm5ic3A7YXJlIGdpdmVuIGFzIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG1heGltdW0gbnVtYmVyIG9mIGJhbGxvb25zIHlvdSBjYW4gYnVzdC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IDxlbT5OPFwvZW0+ICZsZTsgMjUwLDAwMDxcL2xpPlxyXG5cdDxsaT4wICZsZTsgPGVtPkw8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgMTA8c3VwPjE1PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgPGVtPkQ8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPlRoaXMgc3VidGFzayBoYXMgYWRkaXRpb25hbCBjb25zdHJhaW50cy46Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGVtPk48XC9lbT4gJmxlOyAyMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazIiOiI8cD5UaGlzIHN1YnRhc2sgaGFzIGFkZGl0aW9uYWwgY29uc3RyYWludHMuOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxlbT5OPFwvZW0+ICZsZTsgNSwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2szIjoiPHA+VGhpcyBzdWJ0YXNrIGhhcyBubyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiJ9XQ==

출처

University > KAIST > 2018 KAIST RUN Spring Contest T번

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: koosaga

채점

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