On National Chunky Turnip day, Ian Zhang has decided to bless some of his $$$n$$$ fanclubs around the country with his presence. The $$$i$$$-th fanclub is located at $$$x_i$$$ and has $$$m_i$$$ members ($$$1 \le m_i \le 2$$$). The location of each fanclub is distinct from all other fanclubs.
Ian is only able to teleport in the positive direction. In addition, since he is busy doing great geniosity things, after he visits a fanclub with two members, he can only visit fanclubs with two members from then on.
Ian starts off his journey at the Lexington High School Chunky Turnips Fanclub, which is located at point $$$0$$$ and has $$$1\,000\,000\,000$$$ members. Please help him find the maximum number of fanclub members he can visit.
The first line contains $$$n$$$ ($$$1 \le n \le 10^3$$$).
The following $$$n$$$ lines each contain $$$2$$$ integers $$$x_i$$$ and $$$y_i$$$, the position of each fanclub and the number of members ($$$1 \le x_i \le 10^5$$$, $$$1 \le y_i \le 2$$$).
Output a single integer that is the maximum number of fanclub members that Ian can visit.
5 3 1 4 1 5 1 2 2 6 2
1000000005
In the first test, it is better to skip the first fanclub with two members at point $$$2$$$, and instead aim for the three fanclubs with one member at $$$3, 4$$$ and $$$5$$$ before visiting the fanclub at point $$$6$$$. This reaches a total of $$$5$$$ members in addition to the $$$1\,000\,000\,000$$$ members at point $$$0$$$.
Название |
---|