Successfully dealing with all the zombies, Ace realized that he was already at Waterloo. Horrifyingly, he discovers that all the zombies he had shot were actually sleep-deprived computer science students! Specifically, students had been shot. Ace activates his lifeguard training. Using his mad Theory of Knowledge skills, he assigns a value to each of the students' lives. He also analyzes the time they likely have left and the time it will take to save each of them . Being NLS certified, Ace can teleport, and wants to save the most number of lives possible.
However, Ace is bad at calculating things, and needs your help. Your job is to give him the maximum value of people he can save. Note that there may be more than one optimal solution.
Input Specification
The first line will contain one integer .
The next lines will contain three integers , , and .
Output Specification
One line containing the maximum value of people he can save.
Sample Input
4
1 1 2
10000 2 1
3 4 6
2 4 7
Sample Output
4
Explanation
Ace saves person first. He can't save person because he would take seconds, after which the person will have already died. He chooses to save person , using up an additional seconds, and does not have time to save person .
Comments
The values were for the sake of the problem, Ace does not in fact believe in eugenics or assigning value to life. That's the prof's job.