4 人解决，6 人已尝试。
4 份提交通过，共有 36 份提交。
8.0 EMB 奖励。
单点时限: 5.0 sec
内存限制: 512 MB
You may have heard of the lost city of Atlantis. As legend goes, Atlantis was a city of great wealth and power. Then the Gods became displeased with Atlantis and sank it into the ocean. What you may not have heard is the story of Demetrios, the only person in Atlantis with a ship at the time the city was pushed underwater.
Demetrios was an incredibly selfish man and thought of only one thing when he noticed the water level in the city rising: collecting the wealth of accessible gold in Atlantis and transporting it into his ship before the treasure was lost forever. Luckily for Demetrios, when the water level began rising, the many guards keeping safe the gold stores abandoned their posts to seek safety.
Demetrios knows the location of every gold store in Atlantis and how long it will take him to get to a particular store and back to his ship. He also knows the altitude at which each gold store resides, which determines when the store will be swallowed by the rising sea. The trouble is that he’s not sure he’ll have time to make it to every store before they become submerged. He now wonders the maximum number of stores he can visit prior to their respective submersion, if he picks his schedule optimally.
The gold store must remain above water during the ENTIRE trip to and from the store.
The first line of input will contain the integer $n$, ($1 \leq n \leq 200\, 000$), the number of gold stores in Atlantis. The next $n$ lines will contain two integers on each line, $t_i$ and $h_i$, ($1 \leq t_i, h_i \leq 10^9$), the round-trip time in seconds it will take Demetrios to visit store $i$ and return to his ship with the gold, and the feet above sea level of store $i$, respectively.
Output the maximum number of gold stores Demetrios can visit such that each is visited prior to it becoming submerged. Assume sea level rises by one foot every second, starts at height $0$, and begins rising immediately.
5 5 8 5 6 3 4 5 13 6 10
3
5 5 10 6 15 2 7 3 3 4 11
4