Team Work

The UCF Programming Teams have succeeded for over 40 years because of talented, dedicated students and experienced, skilled coaches. The coaches teach algorithms and team strategies, and the students compete in contests.

A team in the International Collegiate Programming Contest has three students. One major team strategy is deciding who solves which problem. The coaches need a program that answers this question. Write that program.

Given the number of students on a team, the number of problems, the time each student needs for each problem, and the total contest time, find the maximum number of problems the whole team can solve in the given time. Assume that:

• A student can solve at most one problem in the entire contest. For example, suppose the contest lasts 5 hours and Student1 can solve Problem7 in 1 hour and Problem9 in 2 hours. Even though both problems fit in 3 hours, Student1 can still solve at most one problem.
• The team has only one computer. While a student uses it, teammates cannot use it, so problems are solved one at a time. For example, suppose the contest lasts 5 hours, Student2 can solve Problem6 in 2 hours, and Student3 can solve Problem8 in 4 hours. Those two problems need 6 hours in total, so the 5-hour contest is not enough to solve both. Problems are not solved in parallel, even with several students.

The first line contains three integers $n$, $p$, and $t$.

• $n$ ($1 \le n \le 200$) is the number of students on the team.
• $p$ ($1 \le p \le 200$) is the number of problems in the set.
• $t$ ($1 \le t \le 10^5$) is the total time available.

The next $n$ lines each contain $p$ integers. Line $i$ describes student $i$. The $j$-th integer on that line is the time student $i$ needs to solve problem $j$, and each value is between $0$ and $10^5$, inclusive. A value of $0$ means that student cannot solve that problem.

Print the maximum number of problems the entire team can solve in the given time.