M. Meta
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Teamwork is critical in programming competitions! Effective communication and solution discussion among team members is key before implementation. Sometimes, team members might choose incorrect solutions and spend excessive time coding them. Other times, someone may suggest a more straightforward and simpler approach.

A team of three members is taking part in the competition. For each team member, you are given the time it takes for them to implement each of the problems. However, they share just one computer, so they could only work on one problem at a time. The contest has a duration of $$$300$$$ minutes. Your task is to compute the maximum number of different problems the team can solve. You can neglect the time required for switching between problems — if the total time required for solving problems doesn't exceed $$$300$$$ minutes, they could do it in time.

Let's look at the sample:

  • The first team member likes geometry and is most effective at implementing problems such as "3D" or "JigsawPuzzle".
  • The second team member likes constructive problems and would be the best for problems like "EqualStrings", "GeoSharding" or "InteractiveCasino". Although the problem "AplusB" may not be time-intensive to implement, the solution idea is not straightforward, so other team members couldn't solve it at all. This team member codes in Java and cannot solve "FastTreeQueries" due to the strict Time Limit.
  • The last team member has a good library with already implemented data structures, so they could implement problems like "TheBestWife" faster than others.
Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 14$$$) — the number of problems in the contest.

Each of the next $$$n$$$ lines contains the description of the problem $$$name$$$ $$$t_1$$$ $$$t_2$$$ $$$t_3$$$ ($$$-1 \le t_i \le 300$$$) — the problem's name and the number of minutes required for each participant to implement it. The problem name consists of at most $$$30$$$ alphanumeric characters. If $$$t_i$$$ equals $$$-1$$$, this team member could not implement this problem at all.

Output

Print single integer — the maximum number of problems the team could solve during the contest.

Example
Input
13
AplusB -1 20 -1
TheBestWife 80 90 60
Cardinality 40 50 30
3D 40 -1 70
EqualStrings 25 15 20
FastTreeQueries 120 -1 40
GeoSharding 25 20 30
HaveYouSeenThisSubarray 80 90 60
InteractiveCasino 50 20 30
JigsawPuzzle 40 50 80
Knapsack -1 40 200
LondonUnderground -1 200 40
Meta 5 7 10
Output
10