GFSSOC '17 S4 - First Ace

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 16M

Authors:
Problem type

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, N (1 \le N \le 10\,000) students had been shot. Ace activates his lifeguard training. Using his mad Theory of Knowledge skills, he assigns a value V (1 \le V \le 10\,000) to each of the students' lives. He also analyzes the time they likely have left T (1 \le T \le 1000) and the time it will take to save each of them S (1 \le S \le 1000). 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 N.

The next N lines will contain three integers V, S, and T.

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 1 first. He can't save person 2 because he would take 2 seconds, after which the person will have already died. He chooses to save person 3, using up an additional 4 seconds, and does not have time to save person 4.


Comments


  • 5
    P234rex  commented on Jan. 20, 2017, 9:06 p.m. edit 2

    The V 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.