Atlantis

잃어버린 도시 아틀란티스에 대해 들어본 적이 있을 것이다. 전설에 따르면 아틀란티스는 막대한 부와 권력을 지닌 도시였으나, 신들의 노여움을 사 바다에 가라앉았다. 하지만 도시가 물에 잠기던 순간 아틀란티스에서 유일하게 배를 가지고 있던 사람인 데메트리오스의 이야기는 들어보지 못했을 것이다.

데메트리오스는 지극히 이기적인 사람이었고, 도시의 수위가 오르는 것을 보고서는 단 한 가지 생각만 했다. 아직 접근 가능한 아틀란티스의 금을 모아 보물이 영영 사라지기 전에 자기 배로 옮기는 것이었다. 다행히도 수위가 오르기 시작하자 금을 지키던 수많은 경비병들이 안전을 찾아 자리를 떠났다.

데메트리오스는 아틀란티스의 모든 금 상점의 위치와, 특정 상점에 갔다가 배로 돌아오는 데 걸리는 시간을 알고 있다. 또한 각 금 상점이 위치한 고도도 알고 있는데, 이는 그 상점이 언제 바다에 잠길지를 결정한다. 문제는 모든 상점이 물에 잠기기 전에 그곳에 도착할 시간이 있을지 확신하지 못한다는 것이다. 그는 이제 일정을 최적으로 짜면 각 상점이 잠기기 전에 방문할 수 있는 상점의 최대 개수가 몇 개인지 궁금해한다.

2017 NCNA Regional 기간에 다음과 같은 해명이 게시되었다. "중요: 금 상점은 그곳에 가고 오는 전체 여정 동안 수면 위에 남아 있어야 한다."

첫째 줄에는 아틀란티스의 금 상점 수를 나타내는 정수 n (1 ≤ n ≤ 200 000)이 주어진다. 다음 n개의 줄에는 두 개의 정수 ti와 hi (1 ≤ ti, hi ≤ 109)가 주어지는데, 각각 데메트리오스가 상점 i를 방문해 금을 가지고 배로 돌아오는 데 걸리는 왕복 시간(초)과 상점 i의 해발 고도(피트)이다.

데메트리오스가 각 상점이 물에 잠기기 전에 방문할 수 있는 금 상점의 최대 개수를 출력한다. 해수면은 매초 1피트씩 상승하며 높이 0에서 시작해 즉시 상승하기 시작한다고 가정한다.