Problem A

Hockey Siblings

Mr Staal has many, many children. All of them play hockey, with various skill levels. He wants to form a team consisting of some of his children to play in a minor league tournament.

During the tournament, teams will be divided into 4 groups. Within each group, each team will play each other team in the group. Then, the top 2 teams from each group will enter the playoffs. (The top 2 teams are chosen by seeing which team wins the most games. If two teams win the same number of games, the team with the largest total number of goals scored is ranked higher. If two teams win the same number of games AND have scored equal numbers goals, then whichever team has a smaller number of goals against is ranked higher. If two teams have won the same number of games and have the same numbers of goals for and against, then the team that has the smaller total number of penalty minutes is ranked higher. If two teams have the same number of wins, goals for and against and penalty minutes, then a coin is flipped to see which team ranks higher.) The eight teams that make it to the playoffs play an elimination tournament. First, in the quarter-finals, pairs of teams play a best-of-five series. Then, the four winners of these series go on to the semi-finals and are again paired off to play in two best-of-five series. The two winners of these series play each other in the finals (another best-of-five series), and the winner of that series is crowned as the SUPREME WINNER of the tournament. During the series, there are no tied games: if a game is tied at the end of the regular three 20-minute periods of play, the game continues into sudden-death overtime until one team scores a goal to break the tie. Overtime play is divided into 20-minute periods with a 10-minute break between periods.

The league has a rule that the total of the ages of all the members on a team can be at most 120. The goal is to choose the most skillful team possible. Each child is at least 1 year old. You may assume that no child is over 120 years old.


Photo sources: hurricanes.nhl.com, teamusa.org, ctvnews.ca

Input

The input will consist of multiple instances. Each instance will begin with a number n of children on a line by itself. You may assume that n is at most 2000. Following this, there will be n lines. Each of these lines contains the first name of a child, followed by the child's age (in years), followed by an integer score indicating the child's skill level. This score will be between 1 and 100 (inclusive). The end of the input will be indicated by a value of n=0. No output should be produced for this input line.

Output

For each input instance, output the maximum sum of scores that can be achieved by choosing a subset of the children for the team, subject to the constraint that the total age is at most 120.

Sample Input

5
Eric 30 92
Marc 28 79
Jordan 26 87
Jared 25 66
Jonas 34 1
10
Tiidrek 24 23
Juri 22 50
Liisa 15 76
Priidu 14 45
Jakob 13 78
Aleksander 11 7
Alviine 10 98
Marja 8 81
Oskar 7 72
Marie 4 16
0

Sample Output

324
539